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

Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn +1

[See the paper for the full abstract.] We show tight upper and lower bounds for time-space trade-offs for the $c$-Approximate Near Neighbor Search problem. For the $d$-dimensional…