33 citations · 33 across the 3 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2015★ 33 cited
Optimal Data-Dependent Hashing for Approximate Near Neighbors
Alexandr Andoni, Ilya Razenshteyn
We show an optimal data-dependent hashing scheme for the approximate near neighbor problem. For an -point data set in a -dimensional space our data structure achieves query t…
cs.DS2012
On Epsilon-Nets, Distance Oracles, and Metric Embeddings
Ilya Razenshteyn
We give two new applications of an observation from \cite{ADFGW11}. The first is an almost linear sized constant time data structure for reporting very large distances in undirecte…