Fetching the paper…
Reading the bibliography…
We prove a tight lower bound for the exponent $\rho$ for data-dependent Locality-Sensitive Hashing schemes, recently used to design efficient solutions for the $c$-approximate nearest neighbor search.
Extensions of Lipschitz mappings into a Hilbert space
William B. Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
The geometry of graphs and some of its algorithmic applications
Nathan Linial, Eran London, and Yuri Rabinovich · 1995
Earlier work this paper cites.
Approximate nearest neighbors: towards removing the curse of dimensionality
Piotr Indyk and Rajeev Motwani · 1998
Earlier work this paper cites.
Efficient search for approximate nearest neighbor in high dimensional spaces
Eyal Kushilevitz, Rafail Ostrovky, and Yuval Rabani · 2000
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.
An elementary proof of a theorem of Johnson and Lindenstrauss
Sanjoy Dasgupta and Anupam Gupta · 2003
Earlier work this paper cites.
Locality-sensitive hashing scheme based on p-stable distributions
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni · 2004
Earlier work this paper cites.
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Alexandr Andoni and Piotr Indyk · 2006
Earlier work this paper cites.
Foundations of Multidimensional and Metric Data Structures
Hannan Samet · 2006
Cited alongside, same era.
Lower bounds on locality sensitive hashing
Rajeev Motwani, Assaf Naor, and Rina Panigrahy · 2007
Cited alongside, same era.
Spherical LSH for approximate nearest neighbor search on unit hypersphere
Kengo Terasawa and Yuzuru Tanaka · 2007
Cited alongside, same era.
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Alexandr Andoni and Piotr Indyk · 2008
Cited alongside, same era.
A geometric approach to lower bounds for approximate near-neighbor search and partial match
Rina Panigrahy, Kunal Talwar, and Udi Wieder · 2008
Cited alongside, same era.
Nearest Neighbor Search: the Old, the New, and the Impossible
Alexandr Andoni · 2009
Cited alongside, same era.
Optimal lower bounds for locality sensitive hashing (except when q is tiny)
Ryan O’Donnell, Yi Wu, and Yuan Zhou · 2011
Later among the works it cites.
Approximate nearest neighbor: towards removing the curse of dimensionality
Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani · 2012
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.
Hashing for similarity search: A survey
Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji · 2014
Later among the works it cites.
Practical and optimal LSH for angular distance
Alexandr Andoni, Piotr Indyk, Michael Kapralov, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt · 2015
Closest in time.
Optimal data-dependent hashing for approximate near neighbors
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Bucketing coding and information theory for the statistical highdimensional nearest-neighbor problem
Moshe Dubiner · 2010
Cited alongside, same era.
Lower bounds on near neighbor search via metric expansion
Rina Panigrahy, Kunal Talwar, and Udi Wieder · 2010
Cited alongside, same era.
Alexandr Andoni and Ilya Razenshteyn · 2015
Closest in time.
New directions in nearest neighbor searching with applications to lattice sieving
Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven · 2015
Closest in time.