261 citations · 836 across the 30 of their papers we have counts for
3 papers · 1 filter
Approximate Near Neighbors for General Symmetric Norms
Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov +2
We show that every symmetric normed space admits an efficient nearest neighbor search data structure with doubly-logarithmic approximation. Specifically, for every , $d = n^{o(1…
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 -Approximate Near Neighbor Search problem. For the -dimensional…
Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors
Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn +1
We show tight lower bounds for the entire trade-off between space and query time for the Approximate Near Neighbor search problem. Our lower bounds hold in a restricted model of co…