Theory Lunch

Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors

Ilya Razenshteyn

September 14, 2016

I will show a new data structure for the Approximate Nearest Neighbor problem for Euclidean and Hamming distances, which has the following benefits:

* It achieves a smooth time-space trade-off, with two extremes being *near-linear* space and *sub-polynomial* query time.
* It unifies, simplifies, and improves upon all previous data structures for the problem.
* It is optimal in an appropriate restricted model.

The data structure can be seen as a combination of Spherical Locality-Sensitive Filtering and *data-dependent* Locality-Sensitive Hashing. Joint work with Alexandr Andoni (Columbia), Thijs Laarhoven (IBM Research Zurich) and Erik Waingarten (Columbia). The preprint is available as http://arxiv.org/pdf/1608.03580v1.pdf .