Sub-linear Memory Sketches for Near Neighbor Search on Streaming Data
This work addresses the memory-accuracy tradeoff for nearest neighbor search in streaming applications like social media friend recommendation, though it is incremental as it builds on existing techniques like LSH and compressed sensing.
The paper tackles the problem of nearest neighbor search on streaming data by developing a sublinear memory sketch that compresses datasets to size O(N^b log^3 N) for b < 1, achieving orders of magnitude better compression than random projection methods while retaining the ability to report nearest neighbors for stable queries.
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.