Fetching the paper…
Reading the bibliography…
The nearest neighbor problem is defined as follows: Given a set $P$ of $n$ points in some metric space $(X,D)$, build a data structure that, given any point $q$, returns a point in $P$ that is closest to $q$ (its "nearest neighbor" in $P$).
Sur quelques points du calcul fonctionnel
M Maurice Fréchet · 1906
Earlier work this paper cites.
Über den variabilitätsbereich der fourierÕschen konstanten von positiven harmonischen funktionen
Constantin Carathéodory · 1911
Earlier work this paper cites.
Quelques problèmes concernant les espaces métriques non-séparables
Casimir Kuratowski · 1935
Earlier work this paper cites.
On certain metric spaces arising from euclidean spaces by a change of metric and their imbedding in hilbert space
Isaac J Schoenberg · 1937
Earlier work this paper cites.
Positive definite functions on spheres
I. J. Schoenberg · 1942
Earlier work this paper cites.
Extremum problems with inequalities as subsidiary conditions
Fritz John · 1948
Earlier work this paper cites.
Perceptrons: An introduction to computational geometry
Marvin Minsky and Seymour A Papert · 1969
Earlier work this paper cites.
Gaussian elimination is not optimal
Volker Strassen · 1969
Earlier work this paper cites.
The dimension of almost spherical sections of convex bodies
Tadeusz Figiel, Joram Lindenstrauss, and Vitali D Milman · 1977
Earlier work this paper cites.
Applications of a planar separator theorem
Richard J Lipton and Robert E Tarjan · 1980
Earlier work this paper cites.
Rapid multiplication of rectangular matrices
Don Coppersmith · 1982
Earlier work this paper cites.
Embedding ℓ p m \ell_{p}^{m} into ℓ 1 n \ell_{1}^{n}
William B Johnson and Gideon Schechtman · 1982
Earlier work this paper cites.
Extensions of lipschitz mappings into a hilbert space
William B Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
On lipschitz embedding of finite metric spaces in hilbert space
Jean Bourgain · 1985
Earlier work this paper cites.
Introduction
Franco P Preparata and Michael Ian Shamos · 1985
Earlier work this paper cites.
A randomized algorithm for closest-point queries
Kenneth L Clarkson · 1988
Earlier work this paper cites.
Approximate nearest neighbor queries in fixed dimensions
Sunil Arya and David M Mount · 1993
Earlier work this paper cites.
Approximate closest-point queries in high dimensions
Marshall Bern · 1993
Earlier work this paper cites.
Point location in arrangements of hyperplanes
Stefan Meiser · 1993
Earlier work this paper cites.
An algorithm for approximate closest-point queries
Kenneth L Clarkson · 1994
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.
Splitters and near-optimal derandomization
Moni Naor, Leonard J Schulman, and Aravind Srinivasan · 1995
Earlier work this paper cites.
Banach spaces for analysts
Przemyslaw Wojtaszczyk · 1996
Earlier work this paper cites.
An elementary introduction to modern convex geometry
Keith Ball · 1997
Earlier work this paper cites.
Syntactic clustering of the web
Andrei Z Broder, Steven C Glassman, Mark S Manasse, and Geoffrey Zweig · 1997
Earlier work this paper cites.
On the resemblance and containment of documents
Andrei Z Broder · 1997
Earlier work this paper cites.
Two algorithms for nearest-neighbor search in high dimensions
Jon M Kleinberg · 1997
Earlier work this paper cites.
On embedding expanders into ℓ p \ell_{p} spaces
Jiří Matoušek · 1997
Earlier work this paper cites.
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Sunil Arya, David M Mount, Nathan S Netanyahu, Ruth Silverman, and Angela Y Wu · 1998
Earlier work this paper cites.
Approximate nearest neighbor queries revisited
Timothy M Chan · 1998
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.
Approximate nearest neighbor algorithms for hausdorff metrics via embeddings
Martin Farach-Colton and Piotr Indyk · 1999
Earlier work this paper cites.
Cell probe complexity-a survey
Peter Bro Miltersen · 1999
Cited alongside, same era.
Dimensionality reduction techniques for proximity problems
Piotr Indyk · 2000
Cited alongside, same era.
High-dimensional computational geometry
Piotr Indyk · 2000
Cited alongside, same era.
Efficient search for approximate nearest neighbor in high dimensional spaces
Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani · 2000
Cited alongside, same era.
Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein · 2001
Cited alongside, same era.
On approximate nearest neighbors under ℓ ∞ \ell_{\infty} norm
Piotr Indyk · 2001
Cited alongside, same era.
New and improved johnson-lindenstrauss embeddings via the restricted isometry property
Felix Krahmer and Rachel Ward · 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.
Nns lower bounds via metric expansion for l∞ and emd
Michael Kapralov and Rina Panigrahy · 2012
Later among the works it cites.
Multiplying matrices faster than coppersmith-winograd
Virginia Vassilevska Williams · 2012
Later among the works it cites.
An almost optimal unrestricted fast johnson-lindenstrauss transform
Nir Ailon and Edo Liberty · 2013
Later among the works it cites.
Optimal bounds for johnson-lindenstrauss transforms and streaming problems with subconstant error
Thathachar S Jayram and David P Woodruff · 2013
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Moses S Charikar · 2002
Cited alongside, same era.
Approximate nearest neighbor algorithms for Fréchet distance via product metrics
Piotr Indyk · 2002
Cited alongside, same era.
Fast image retrieval via embeddings
Piotr Indyk and Nitin Thaper · 2003
Cited alongside, same era.
Locality-sensitive hashing scheme based on p-stable distributions
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni · 2004
Cited alongside, same era.
Approximate nearest neighbor under edit distance via product metrics
Piotr Indyk · 2004
Cited alongside, same era.
On the impossibility of dimension reduction in ℓ 1 {\ell_{1}}
Bo Brinkman and Moses Charikar · 2005
Cited alongside, same era.
Later among the works it cites.
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
Later among the works it cites.
Beyond locality-sensitive hashing
Alexandr Andoni, Piotr Indyk, Huy L Nguyên, and Ilya Razenshteyn · 2014
Later among the works it cites.
Essential coding theory
Venkatesan Guruswami, Atri Rudra, and Madhu Sudan · 2014
Later among the works it cites.
Sparser johnson-lindenstrauss transforms
Daniel M. Kane and Jelani Nelson · 2014
Later among the works it cites.
Approximate nearest line search in high dimensions
Sepideh Mahabadi · 2014
Later among the works it cites.
Algorithms for High Dimensional Data
Huy L. Nguyên · 2014
Later among the works it cites.
New constructions of RIP matrices with fast multiplication and fewer rows
Jelani Nelson, Eric Price, and Mary Wootters · 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.
Hashing for similarity search: A survey
Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji · 2014
Later among the works it cites.
Optimal data-dependent hashing for approximate near neighbors
Alexandr Andoni and Ilya Razenshteyn · 2015
Later among the works it cites.
Yair Bartal and Lee-Ad Gottlieb · 2015
Later among the works it cites.
Smooth tradeoffs between insert and query complexity in nearest neighbor search
Michael Kapralov · 2015
Later among the works it cites.
Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
Gregory Valiant · 2015
Later among the works it cites.
Polynomial representations of threshold functions and algorithmic applications
Josh Alman, Timothy M Chan, and Ryan Williams · 2016
Later among the works it cites.
On the complexity of maximum inner product search
Thomas D Ahle, Rasmus Pagh, Ilya Razenshteyn, and Francesco Silvestri · 2016
Later among the works it cites.
Tight lower bounds for data-dependent locality-sensitive hashing
Alexandr Andoni and Ilya P. Razenshteyn · 2016
Later among the works it cites.
A faster subquadratic algorithm for finding outlier correlations
Matti Karppa, Petteri Kaski, and Jukka Kohonen · 2016
Later among the works it cites.
Locality-sensitive hashing without false negatives
Rasmus Pagh · 2016
Later among the works it cites.
Learning to hash for indexing big data: a survey
Jun Wang, Wei Liu, Sanjiv Kumar, and Shih-Fu Chang · 2016
Later among the works it cites.
Optimal las vegas locality sensitive data structures
Thomas Dybdahl Ahle · 2017
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
Later among the works it cites.
Data-dependent hashing via nonlinear spectral gaps
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten · 2017
Later among the works it cites.
Approximate near neighbors for general symmetric norms
Alexandr Andoni, Huy L Nguyên, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten · 2017
Later among the works it cites.
A spectral gap precludes low-dimensional embeddings
Assaf Naor · 2017
Later among the works it cites.
High-Dimensional Similarity Search and Sketching: Algorithms and Hardness
Ilya Razenshteyn · 2017
Later among the works it cites.
On some fine-grained questions in algorithms and complexity
V. Williams · 2018
Closest in time.