Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Communications of the ACMPublished 1 January 2008Open access
Alexandr Andoni, Piotr Indyk
Citations1,458
SJR quartileQ1
SJR score1.15
SNIP3.34
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An algorithm for the c-approximate nearest neighbor problem in a d-dimensional Euclidean space, achieving query time of O(dn 1c2/+o(1)) and space O(DN + n1+1c2 + o(1) + 1/c2), which almost matches the lower bound for hashing-based algorithm recently obtained.
Abstract
In this article, we give an overview of efficient algorithms for the approximate and exact nearest neighbor problem. The goal is to preprocess a dataset of objects (e.g., images) so that later, given a new query object, one can quickly return the dataset object that is most similar to the query. The problem is of significant interest in a wide variety of areas.
Keywords
Computer Science
Communications of the ACMMultidimensional binary search trees used for associative searching
7,467 Citations1975Jon Bentley
The multidimensional binary search tree (or k-d tree) as a data structure for storage of information to be retrieved by associative searches is developed and it is shown to be quite efficient in its storage requirements.
Journal of the ACMImproved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
3,684 Citations1995Michel X. Goemans, David P. Williamson
This algorithm gives the first substantial progress in approximating MAX CUT in nearly twenty years, and represents the first use of semidefinite programming in the design of approximation algorithms.
American Mathematical MonthlySphere Packings, Lattices and Groups.
3,443 Citations1989H. S. M. Coxeter, J. H. Conway +1 more
Similarity Search in High Dimensions via Hashing
3,108 Citations1999Aristides Gionis, Piotr Indyk +1 more
Experimental results indicate that the novel scheme for approximate similarity search based on hashing scales well even for a relatively large number of dimensions, and provides experimental evidence that the method gives improvement in running time over other methods for searching in highdimensional spaces based on hierarchical tree decomposition.
Locality-sensitive hashing scheme based on p-stable distributions
2,917 Citations2004Mayur Datar, Nicole Immorlica +2 more
A novel Locality-Sensitive Hashing scheme for the Approximate Nearest Neighbor Problem under lp norm, based on p-stable distributions that improves the running time of the earlier algorithm and yields the first known provably efficient approximate NN algorithm for the case p<1.
Similarity estimation techniques from rounding algorithms
2,186 Citations2002Moses Charikar
It is shown that rounding algorithms for LPs and SDPs used in the context of approximation algorithms can be viewed as locality sensitive hashing schemes for several interesting collections of objects.
On the resemblance and containment of documents
1,666 Citations2002Arndt Bröder
The basic idea is to reduce these issues to set intersection problems that can be easily evaluated by a process of random sampling that could be done independently for each document.
Foundations of Multidimensional and Metric Data Structures
1,379 Citations2006Hanan Samet, Jim Gray
This is a life's work by the author who is clearly the best person for the job and the need for a comprehensive book on the subject is paramount.
Computer Networks and ISDN SystemsSyntactic clustering of the Web
1,347 Citations1997Andrei Broder, S. Glassman +2 more
An efficient way to determine the syntactic similarity of files is developed and applied to every document on the World Wide Web, and a clustering of all the documents that are syntactically similar is built.
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
1,099 Citations2006Alexandr Andoni, Piotr Indyk
Cambridge University Press eBooksThe Volume of Convex Bodies and Banach Space Geometry
1,001 Citations1989Gilles Pisier
Journal of Computer and System SciencesMin-Wise Independent Permutations
833 Citations2000Andrei Broder, Moses Charikar +2 more
Journal of Computational BiologyFinding Motifs Using Random Projections
537 Citations2002Jeremy Buhler, Martin Tompa
SIAM Journal on ComputingThe Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
481 Citations2009Nir Ailon, Bernard Chazelle
A new low-distortion embedding of $\ell-2^d$ into $\ell_p^{O(\log n)}$ ($p=1,2$) called the fast Johnson-Lindenstrauss transform (FJLT) is introduced, based upon the preconditioning of a sparse projection matrix with a randomized Fourier transform.
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
397 Citations2006Nir Ailon, Bernard Chazelle
A new low-distortion embedding of l2d into l p (p=1,2) is introduced, called the Fast-Johnson-Linden-strauss-Transform (FJLT), based upon the preconditioning of a sparse projection matrix with a randomized Fourier transform.
Min-wise independent permutations (extended abstract)
352 Citations1998Andrei Broder, Moses Charikar +2 more
This research was motivated by the fact that such a family of permutations is essential to the algorithm used in practice by the AltaVista web index software to detect and filter near-duplicate documents.
Two algorithms for nearest-neighbor search in high dimensions
347 Citations1997Jon Kleinberg
A new approach to the nearest-neighbor problem is developed, based on a method for combining randomly chosen one-dimensional projections of the underlying point set, which results in an algorithm for finding e-approximate nearest neighbors with a query time of O((d log d)(d + log n)).
Navigating nets: simple algorithms for proximity search
319 Citations2015Robert Krauthgamer, James R. Lee
BioinformaticsEfficient large-scale sequence comparison by locality-sensitive hashing
266 Citations2001Jeremy Buhler
A new algorithm is introduced, LSH-ALL-PAIRS, to find ungapped local alignments in genomic sequence with up to a specified fraction of substitutions, found to be both efficient and sensitive for finding local similarities with as little as 63% identity in mammalian genomic sequences up to tens of megabases in length.
Efficient search for approximate nearest neighbor in high dimensional spaces
256 Citations1998Eyal Kushilevitz, Rafail Ostrovsky +1 more
Significantly improving and extending recent results of Kleinberg, data structures whose size is polynomial in the size of the database and search algorithms that run in time nearly linear or nearly quadratic in the dimension are constructed.
IEEE Transactions on Neural NetworksNearest-Neighbor Methods in Learning and Vision (Shakhnarovich, G. et al., Eds.; 2006) [Book review]
230 Citations2008Francesco Gianfelici
This volume brings together contributions of top-level researchers in theory of computation, machine learning, and computer vision with the goal of closing up the gaps between disciplines and current state-of-the-art methods for emerging applications.
Randomized algorithms and NLP
210 Citations2005Deepak Ravichandran, Patrick Pantel +1 more
The power of randomized algorithm is explored to address the challenge of working with very large amounts of data and the running time from quadratic to practically linear in the number of elements to be computed.
The geometry of graphs and some of its algorithmic applications
189 Citations2002Nathan Linial, Eran London +1 more
Efficient algorithms for embedding graphs low-dimensionally with a small distortion, and a new deterministic polynomial-time algorithm that finds a (nearly tight) cut meeting this bound.
Symposium on Discrete AlgorithmsEntropy based nearest neighbor search in high dimensions
186 Citations2006Rina Panigrahy
Approximating a finite metric by a small number of tree metrics
172 Citations2002Moses Charikar, Chandra Chekuri +3 more
This paper derandomizes the use of Bartal's algorithm and obtains the first deterministic approximation algorithms for buy-at-bulk network design and vehicle routing and a novel view of probabilistic approximation of metric spaces as a deterministic optimization problem via linear programming.
Finding motifs using random projections
166 Citations2001Jeremy Buhler, Martin Tompa
A novel motif discovery algorithm based on the use of random projections of the input's substrings is introduced that performs better than existing algorithms and typically solves the difficult (14,4)-, (16,5)-, and (18,6)-motif problems quite efficiently.
IEEE Transactions on Information TheorySoft decoding techniques for codes and lattices, including the Golay code and the Leech lattice
165 Citations1986J. Conway, N. J. A. Sloane
Ami are used to obtain new and faster decoding algorithms for the Gosset lattice E_{8} , the Golay code the Leech lattice and some general methods are given for constructing such algorithms.
Scalable Techniques for Clustering the Web.
149 Citations2000Taher H. Haveliwala, Aristides Gionis +1 more
This paper aims to efficiently cluster similar pages on the web, using the technique of Locality-Sensitive Hashing (LSH), in which web pages are hashed in such a way that similar pages have a much higher probability of collision than dissimilar pages.
A replacement for Voronoi diagrams of near linear size
149 Citations2001Sariel Har-Peled
A new type of space decomposition that provides an /spl epsi/-approximation to the distance function associated with the Voronoi diagram of P, while being of near linear size, for d/spl ges/2.
Random Structures and AlgorithmsOn the optimality of the random hyperplane rounding technique for MAX CUT
128 Citations2002Uriel Feige, Gideon Schechtman
There are graphs and optimal embeddings for which the best hyperplane approximates opt within a ratio no better than α, even in the presence of additional valid constraints, which strengthens a result of Karloff that applied only to the expected number of edges cut by a random hyperplane.
High-dimensional computational geometry
116 Citations2000Rajeev Motwani, Piotr Indyk
This thesis shows that it is in fact possible to obtain efficient algorithms for the nearest neighbor problem and a wide range of metrics, including Euclidean, Manhattan or maximum norms and Hausdorff metrics; some of the results hold even for general metrics.
On the Optimality of the Dimensionality Reduction Method
101 Citations2006Alexandr Andoni, Piotr Indyk +1 more
This work shows that any data structure for the (1 + epsi)-approximate nearest neighbor problem in Hamming space, which uses constant number of probes to answer each query, must use nOmega(1/epsi2) space, and investigates the optimality of (1+epsi-approximation algorithms obtained via the dimensionality reduction method.
Approximate graph coloring by semidefinite programming
101 Citations2002David R. Karger, R. Motwani +1 more
A randomized polynomial time algorithm which colors a 3-colorable graph on n vertices with min {O(/spl Delta//sup 1/3/log/sup 4/3//spl Delta/), O(n/Sup 1/4/ log n)} colors is given, marking the first non-trivial approximation result as a function of the maximum degree /spl Delta/.
FLASH: a fast look-up algorithm for string homology
98 Citations2002Andrea Califano, Isidore Rigoutsos
The algorithm presented is based on a probabilistic indexing framework which requires minimal access to the database for each match, and is shown to scale well to databases containing billions of nucleotides with performances that are orders of magnitude better than the fastest of the current techniques.
Multi-index hashing for information retrieval
97 Citations2002Derek Greene, Michal Parnas +1 more
A technique for building hash indices for a large dictionary of strings that permits robust retrieval of strings from the dictionary even when the query pattern has a significant number of errors.
Lecture notes in computer scienceSpherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere
79 Citations2007Kengo Terasawa, Yuzuru Tanaka
A variant of the LSH algorithm for solving the c-approximate nearest neighbor problem in high dimensional spaces is presented, focusing on the special case of where all points in the dataset lie on the surface of the unit hypersphere in a d-dimensional Euclidean space.
IEEE Transactions on Information TheoryGeneralized minimum-distance decoding of Euclidean-space codes and lattices
72 Citations1996G. David Forney, Alexander Vardy
It appears to be practically feasible to implement algebraic multistage GMD decoders for high-dimensional sphere packings, and thus achieve high effective coding gains.
IEEE Transactions on Information TheoryMaximum likelihood decoding of the Leech lattice
63 Citations1993Alexander Vardy, Y. Be'ery
An algorithm for maximum likelihood decoding of the Leech lattice is presented and it is shown that this algorithm is about half the worst case and the average complexity of the best previously known algorithm.
Lower bounds on locality sensitive hashing
55 Citations2006Rajeev Motwani, Assaf Naor +1 more
It is shown that for X=1 it is impossible to achieve ⊇ ≤ 1/2c.
Efficient algorithms for substring near neighbor problem
26 Citations2006Alexandr Andoni
Scalable Techniques for Clustering the Web (Extended Abstract)
20 Citations2000Taher H. Haveliwala, Aristides Gionis +1 more
This paper aims to efficiently cluster similar pages on the web, using the technique of Locality-Sensitive Hashing (LSH), in which web pages are hashed in such a way that similar pages have a much higher probability of collision than dissimilar pages.
Journal of Chemical Information and ModelingScalable Partitioning and Exploration of Chemical Spaces Using Geometric Hashing
20 Citations2005Debojyoti Dutta, Rajarshi Guha +2 more
A data mining framework built on top of a recently developed fast approximate nearest-neighbor-finding algorithm called locality-sensitive hashing (LSH) that can be used to mine huge chemical spaces in a scalable fashion using very modest computational resources is introduced.
The bit vector intersection problem
19 Citations2002Richard M. Karp, Orli Waarts +1 more
It is shown that a fundamental problem arising in the Human Genome Project is captured by the bit vector intersection problem and hence can be solved by the two randomized algorithms presented.
Information and ComputationThe Light Bulb Problem
17 Citations1995Ramamohan Paturi, Sanguthevar Rajasekaran +1 more
The problem of correlational learning is considered and efficient algorithms to determine correlated objects are presented and it is shown that correlation among correlated objects is positively correlated.
IEEE Transactions on CommunicationsEfficient bounded-distance decoding of the hexacode and associated decoders for the Leech lattice and the Golay code
14 Citations1996Ofer Amrani, Y. Be'ery