Loading...

Ilya Razenshteyn on "Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors"

953 views

Loading...

Loading...

Loading...

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 .

Loading...

When autoplay is enabled, a suggested video will automatically play next.

Up next


to add this to Watch Later

Add to

Loading playlists...