Rating is available when the video has been rented.
This feature is not available right now. Please try again later.
Published on Sep 23, 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 .