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.

本条研究提出了史上首个可查询到数据集中最近邻居的亚线性内存草图，并利用局部敏感哈希（LSH）估计器、在线核密度估计和压缩感知相结合来实现稳定查询的子线性内存性能，以取得内存 - 精度权衡的理论效果。