261 citations · 836 across the 30 of their papers we have counts for
3 papers · 1 filter
Beyond Locality-Sensitive Hashing
Alexandr Andoni, Piotr Indyk, Huy L. Nguyen +1
We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in R^d, our algorithm achieves O(n^ρ + d log n) query time an…
Separating Hierarchical and General Hub Labelings
Andrew V. Goldberg, Ilya Razenshteyn, Ruslan Savchenko
In the context of distance oracles, a labeling algorithm computes vertex labels during preprocessing. An query computes the corresponding distance from the labels of and…
On Model-Based RIP-1 Matrices
Piotr Indyk, Ilya Razenshteyn
The Restricted Isometry Property (RIP) is a fundamental property of a matrix enabling sparse recovery. Informally, an m x n matrix satisfies RIP of order k in the l_p norm if ||Ax|…