Fetching the paper…
Reading the bibliography…
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 optimal running time exponent.
A dozen de Finetti-style results in search of a theory
Persi Diaconis and David Freedman · 1987
Earlier work this paper cites.
Similarity estimation techniques from rounding algorithms
Moses S. Charikar · 2002
Earlier work this paper cites.
On the optimality of the random hyperplane rounding technique for MAX CUT
Uriel Feige and Gideon Schechtman · 2002
Earlier work this paper cites.
Nearest-Neighbor Methods in Learning and Vision: Theory and Practice
Gregory Shakhnarovich, Trevor Darrell, and Piotr Indyk · 2005
Earlier work this paper cites.
Foundations of multidimensional and metric data structures
Hanan Samet · 2006
Earlier work this paper cites.
Multi-probe lsh: efficient indexing for high-dimensional similarity search
Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li · 2007
Earlier work this paper cites.
Spherical lsh for approximate nearest neighbor search on unit hypersphere
Kengo Terasawa and Yuzuru Tanaka · 2007
Earlier work this paper cites.
Lower bounds on locality sensitive hashing
Rajeev Motwani, Assaf Naor, and Rina Panigrahy · 2007
Earlier work this paper cites.
Locality sensitive hash functions based on concomitant rank order statistics
Kave Eshghi and Shyamsundar Rajaram · 2008
Earlier work this paper cites.
The fast Johnson–Lindenstrauss transform and approximate nearest neighbors
Nir Ailon and Bernard Chazelle · 2009
Cited alongside, same era.
Feature hashing for large scale multitask learning
Kilian Q. Weinberger, Anirban Dasgupta, John Langford, Alexander J. Smola, and Josh Attenberg · 2009
Cited alongside, same era.
Bucketing coding and information theory for the statistical high-dimensional nearest-neighbor problem
Moshe Dubiner · 2010
Cited alongside, same era.
Product quantization for nearest neighbor search
Hervé Jégou, Matthijs Douze, and Cordelia Schmid · 2011
Cited alongside, same era.
Fast locality-sensitive hashing
Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós · 2011
Cited alongside, same era.
Approximate nearest neighbor: Towards removing the curse of dimensionality
Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani · 2012
UCI machine learning repository, 2013
Moshe Lichman · 2013
Later among the works it cites.
Beyond locality-sensitive hashing
Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, and Ilya Razenshteyn · 2014
Later among the works it cites.
Large-scale speaker identification
Ludwig Schmidt, Matthew Sharifi, and Ignacio Lopez Moreno · 2014
Later among the works it cites.
Densifying one permutation hashing via rotation for fast near neighbor search
Anshumali Shrivastava and Ping Li · 2014
Later among the works it cites.
Optimal lower bounds for locality-sensitive hashing (except when q is tiny)
Ryan O’Donnell, Yi Wu, and Yuan Zhou · 2014
Later among the works it cites.
Fast and RIP-optimal transforms
Nir Ailon and Holger Rauhut · 2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Fast near neighbor search in high-dimensional binary data
Anshumali Shrivastava and Ping Li · 2012
Cited alongside, same era.
Optimal parameters for locality-sensitive hashing
Malcolm Slaney, Yury Lifshits, and Junfeng He · 2012
Cited alongside, same era.
Streaming similarity search over one billion tweets using parallel locality-sensitive hashing
Narayanan Sundaram, Aizana Turmukhametova, Nadathur Satish, Todd Mostak, Piotr Indyk, Samuel Madden, and Pradeep Dubey · 2013
Cited alongside, same era.
Optimal data-dependent hashing for approximate near neighbors
Alexandr Andoni and Ilya Razenshteyn · 2015
Closest in time.
Tight lower bounds for data-dependent locality-sensitive hashing, 2015
Alexandr Andoni and Ilya Razenshteyn · 2015
Closest in time.