Sub-linear Memory Sketches for Near Neighbor Search on Streaming Data

Benjamin Coleman, Richard Baraniuk, Anshumali Shrivastava
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:2089-2099, 2020.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-coleman20a, title = {Sub-linear Memory Sketches for Near Neighbor Search on Streaming Data}, author = {Coleman, Benjamin and Baraniuk, Richard and Shrivastava, Anshumali}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {2089--2099}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/coleman20a/coleman20a.pdf}, url = {https://proceedings.mlr.press/v119/coleman20a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Sub-linear Memory Sketches for Near Neighbor Search on Streaming Data %A Benjamin Coleman %A Richard Baraniuk %A Anshumali Shrivastava %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-coleman20a %I PMLR %P 2089--2099 %U https://proceedings.mlr.press/v119/coleman20a.html %V 119 %X 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.
APA
Coleman, B., Baraniuk, R. & Shrivastava, A.. (2020). Sub-linear Memory Sketches for Near Neighbor Search on Streaming Data. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:2089-2099 Available from https://proceedings.mlr.press/v119/coleman20a.html.

Related Material