33 citations · 41 across the 4 of their papers we have counts for
Showing cs.DSShow all
3 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.DS2014★ 6 cited
Spectral Approaches to Nearest Neighbor Search
Amirali Abdullah, Alexandr Andoni, Ravindran Kannan +1
We study spectral algorithms for the high-dimensional Nearest Neighbor Search problem (NNS). In particular, we consider a semi-random setting where a dataset in …
cs.DS2010★ 2 cited
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
We present a near-linear time algorithm that approximates the edit distance between two strings within a polylogarithmic factor; specifically, for strings of length n and every fix…