261 citations · 836 across the 30 of their papers we have counts for
5 papers · 1 filter
On the Complexity of Inner Product Similarity Join
Thomas D. Ahle, Rasmus Pagh, Ilya Razenshteyn +1
A number of tasks in classification, information retrieval, recommendation systems, and record linkage reduce to the core problem of inner product similarity join (IPS join): ident…
Practical and Optimal LSH for Angular Distance
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven +2
We show the existence of a Locality-Sensitive Hashing (LSH) family for the angular distance that yields an approximate Near Neighbor Search algorithm with the asymptotically optima…
Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing
Alexandr Andoni, Ilya Razenshteyn
We prove a tight lower bound for the exponent for data-dependent Locality-Sensitive Hashing schemes, recently used to design efficient solutions for the -approximate nearest…
Nearly-optimal bounds for sparse recovery in generic norms, with applications to -median sketching
Arturs Backurs, Piotr Indyk, Eric Price +2
We initiate the study of trade-offs between sparsity and the number of measurements in sparse recovery schemes for generic norms. Specifically, for a norm , sparsity par…
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…