Fetching the paper…
Reading the bibliography…
We consider tradeoffs between the query and update complexities for the (approximate) nearest neighbor problem on the sphere, extending the recent spherical filters to sparse regimes and generalizing the scheme and analysis to account for different tradeoffs.
Extensions of Lipschitz mappings into a Hilbert space
William B. Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
An optimal algorithm for approximate nearest neighbor searching in fixed dimensions
Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu · 1994
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.
Similarity search in high dimensions via hashing
Aristides Gionis, Piotr Indyk, and Rajeev Motwani · 1999
Earlier work this paper cites.
Pattern Classification (2nd Edition)
Richard O. Duda, Peter E. Hart, and David G. Stork · 2000
Earlier work this paper cites.
Efficient search for approximate nearest neighbor in high dimensional spaces
Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani · 2000
Earlier work this paper cites.
Database-friendly random projections
Dimitris Achlioptas · 2001
Earlier work this paper cites.
Exact L ∞ L_{\infty} nearest neighbor search in high dimensions
Helmut Alt and Laura Heinrich-Litan · 2001
Earlier work this paper cites.
Similarity estimation techniques from rounding algorithms
Moses S. Charikar · 2002
Earlier work this paper cites.
Locality-sensitive hashing scheme based on p p -stable distributions
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni · 2004
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.
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Alexandr Andoni and Piotr Indyk · 2006
Earlier work this paper cites.
On the optimality of the dimensionality reduction method
Alexandr Andoni, Piotr Indyk, and Mihai Pǎtraşcu · 2006
Earlier work this paper cites.
Pattern Recognition and Machine Learning (Information Science and Statistics)
Christopher M. Bishop · 2006
Earlier work this paper cites.
Very sparse random projections
Ping Li, Trevor J. Hastie, and Kenneth W. Church · 2006
Cited alongside, same era.
Entropy based nearest neighbor search in high dimensions
Rina Panigrahy · 2006
Cited alongside, same era.
Multi-probe LSH: efficient indexing for high-dimensional similarity search
Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li · 2007
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.
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.
Large-scale speaker identification
Ludwig Schmidt, Matthew Sharifi, and Ignacio Lopez-Moreno · 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, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt · 2015
Closest in time.
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
Alexandr Andoni and Ilya Razenshteyn · 2015
Closest in time.
Efficient (ideal) lattice sieving using cross-polytope LSH
Anja Becker and Thijs Laarhoven · 2015
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Space-time tradeoffs for approximate nearest neighbor searching
Sunil Arya, Theocharis Malamatos, and David M. Mount · 2009
Cited alongside, same era.
Nearest Neighbor Search: the Old, the New, and the Impossible
Alexandr Andoni · 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.
Faster exponential time algorithms for the shortest vector problem
Daniele Micciancio and Panagiotis Voulgaris · 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.
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.
Closest in time.
Applications of nearest neighbor search techniques to the BKW algorithm (draft)
Gottfried Herold · 2015
Closest in time.
Smooth tradeoffs between insert and query complexity in nearest neighbor search
Michael Kapralov · 2015
Closest in time.
Sieving for shortest vectors in lattices using angular locality-sensitive hashing
Thijs Laarhoven · 2015
Closest in time.
Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
Thijs Laarhoven and Benne de Weger · 2015
Closest in time.
On computing nearest neighbors with applications to decoding of binary linear codes
Alexander May and Ilya Ozerov · 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 · 2016
Closest in time.
Locality-sensitive hashing without false negatives
Rasmus Pagh · 2016
Closest in time.