We present the first sublinear memory sketch which can be queried to find the v nearest neighbors in a dataset. Our online sketching algorithm can compress an N-element dataset to a sketch of size O(N^b \log ^3{N ) in O(N^{  b+1  } \log ^3{N ) time, where b < 1 when the query satisfies a data-dependent near-neighbor stability condition . We achieve data-dependent sublinear space by combining recent advances in locality sensitive hashing (LSH)-based estimators with compressed sensing. Our  results shed new light on the memory-accuracy tradeoff for near-neighbor search. The techniques presented reveal a deep connection between the fundamental compressed sensing (or heavy hitters) recovery problem and near-neighbor search, leading to new insight for geometric search problems and implications for sketching algorithms .
We present the first sublinear memory sketch that can be queried to find the nearest neighbors in a dataset. Our online sketching algorithm compresses an N element dataset to a sketch of size O(N^b \log ^3 N ) in O(N^{ ( b+1 ) } \log ^3 N ) time, where b < 1. This sketch can correctly report the nearest neighbors of any query that satisfies a stability condition parameterized by b . We achieve sublinear memory performance on stable queries by combining recent advances in locality sensitive hash (LSH)-based estimators , online kernel density estimation, and compressed sensing. Our theoretical results shed new light on the memory-accuracy tradeoff for nearest neighbor search, and our sketch, which consists entirely of short integer arrays, has a variety of attractive features in practice. We evaluate the memory-recall tradeoff of our method on a friend recommendation task in the Google Plus social media network. We obtain orders of magnitude better compression than the random projection based alternative while retaining the ability to report the nearest neighbors of practical queries .
R
which
that
D
v
R
can compress an N-element
compresses an N element
R
^3{N
^3 N
A
(
A
)
R
^3{N
^3 N
R
1 when the query satisfies a data-dependent near-neighbor stability condition
1. This sketch can correctly report the nearest neighbors of any query that satisfies a stability condition parameterized by b
R
data-dependent sublinear space
sublinear memory performance on stable queries
R
hashing
hash
R
with
, online kernel density estimation, and
A
theoretical
R
near-neighbor search. The techniques presented reveal a deep connection between the fundamental compressed sensing (or heavy hitters) recovery problem and near-neighbor search, leading to new insight for geometric search problems and implications for sketching algorithms
nearest neighbor search, and our sketch, which consists entirely of short integer arrays, has a variety of attractive features in practice. We evaluate the memory-recall tradeoff of our method on a friend recommendation task in the Google Plus social media network. We obtain orders of magnitude better compression than the random projection based alternative while retaining the ability to report the nearest neighbors of practical queries