Fetching the paper…
Reading the bibliography…
We take a first step towards a rigorous asymptotic analysis of graph-based approaches for finding (approximate) nearest neighbors in high-dimensional spaces, by analyzing the complexity of (randomized) greedy walks on the approximate near neighbor graph.
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.
Connectivity of the mutual k k -nearest-neighbor graph in clustering and outlier detection
M.R. Brito, E.L. Chavez, A.J. Quiroz, and J.E. Yukich · 1997
Earlier work this paper cites.
On nearest-neighbor graphs
David Eppstein, Michael S. Paterson, and F. Frances Yao · 1997
Earlier work this paper cites.
Separators for sphere-packings and nearest neighbor graphs
Gary L. Miller, Shang-Hua Teng, William Thurston, and Stephen A. Vavasis · 1997
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.
Pattern Classification (2nd Edition)
Richard O. Duda, Peter E. Hart, and David G. Stork · 2000
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.
LSH forest: self-tuning indexes for similarity search
Mayank Bawa, Tyson Condie, and Prasanna Ganesan · 2005
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.
Pattern Recognition and Machine Learning (Information Science and Statistics)
Christopher M. Bishop · 2006
Earlier work this paper cites.
Distributed computation of the k k nn graph for large high-dimensional point sets
Erion Plaku and Lydia E. Kavraki · 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.
The Probabilistic Method
Noga Alon and Joel H. Spencer · 2008
Earlier work this paper cites.
Fast approximate k k NN graph construction for high dimensional data via recursive Lanczos bisection
Jie Chen, Haw-ren Fang, and Yousef Saad · 2009
Earlier work this paper cites.
Datasets for approximate nearest neighbor search, 2010
Laurent Amsaleg and Hervé Jégou · 2010
Cited alongside, same era.
Fast construction of k k -nearest neighbor graphs for point clouds
Michael Connor and Piyush Kumar · 2010
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.
Efficient k k -nearest neighbor graph construction for generic similarity measures
Wei Dong, Moses Charikar, and Kai Li · 2011
Cited alongside, same era.
Fast approximate nearest-neighbor search with k k -nearest neighbor graph
Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, and Hong Zhang · 2011
On computing nearest neighbors with applications to decoding of binary linear codes
Alexander May and Ilya Ozerov · 2015
Later among the works it cites.
New directions in nearest neighbor searching with applications to lattice sieving
Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven · 2016
Later among the works it cites.
Efficient (ideal) lattice sieving using cross-polytope LSH
Anja Becker and Thijs Laarhoven · 2016
Later among the works it cites.
ANN benchmarks – available online at https://github.com/erikbern/ann-benchmarks , 2016
Erik Bernhardsson · 2016
Later among the works it cites.
KGraph – available online at http://kgraph.org/ , 2016
Wei Dong · 2016
Later among the works it cites.
Finding closest lattice vectors using approximate Voronoi cells
Thijs Laarhoven · 2016
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Approximate nearest neighbor search small world approach
Alexander Ponomarenko, Yury Malkov, Andrey Logvinov, and Vladimir Krylov · 2011
Cited alongside, same era.
Scalable k k -nn graph construction for visual descriptors
Jing Wang, Jingdong Wang, Gang Zeng, Zhuowen Tu, Rui Gan, and Shipeng Li · 2012
Cited alongside, same era.
FLANN – available online at https://www.cs.ubc.ca/research/flann/ , 2013
Marius Muja and David G. Lowe · 2013
Cited alongside, same era.
Beyond locality-sensitive hashing
Alexandr Andoni, Piotr Indyk, Huy Lê Nguyên, and Ilya Razenshteyn · 2014
Cited alongside, same era.
Approximate nearest neighbor algorithm based on navigable small world graphs
Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov · 2014
Cited alongside, same era.
Glove: Global vectors for word representation
Jeffrey Pennington, Richard Socher, and Christopher D. Manning · 2014
Cited alongside, same era.
Later among the works it cites.
Y.A. Malkov and D.A. Yashunin · 2016
Later among the works it cites.
FALCONN – available online at https://falconn-lib.org/ , 2016
Ilya Razenshteyn and Ludwig Schmidt · 2016
Later among the works it cites.
Optimal hashing-based time-space trade-offs for approximate near neighbors
Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, and Erik Waingarten · 2017
Closest in time.
LSH forest: Practical algorithms made theoretical
Alexandr Andoni, Ilya Razenshteyn, and Negev Shekel Nosatzki · 2017
Closest in time.
ANN benchmarks – available online at http://sss.projects.itu.dk/ann-benchmarks/ , 2017
Martin Aumueller, Erik Bernhardsson, and Alexander Faithfull · 2017
Closest in time.
ANN-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms
Martin Aumueller, Erik Bernhardsson, and Alexander Faithfull · 2017
Closest in time.
ANNOY – available online at https://github.com/spotify/annoy , 2017
Erik Bernhardsson · 2017
Closest in time.
NMSLib – available online at https://github.com/searchivarius/nmslib , 2017
Leonid Boytsov and Bilegsaikhan Naidan · 2017
Closest in time.
A framework for similarity search with space-time tradeoffs using locality-sensitive filtering
Tobias Christiani · 2017
Closest in time.
Fast cross-polytope locality-sensitive hashing
Christopher Kennedy and Rachel Ward · 2017
Closest in time.
Hypercube LSH for approximate near neighbors
Thijs Laarhoven · 2017
Closest in time.