Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Top Cited Papers
- 1 January 2008
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 51 (1), 117-122
- https://doi.org/10.1145/1327452.1327494
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
Funding Information
- National Science Foundation (CCR-0133849)
This publication has 17 references indexed in Scilit:
- Approximate nearest neighbors and the fast Johnson-Lindenstrauss transformPublished by Association for Computing Machinery (ACM) ,2006
- Scalable Partitioning and Exploration of Chemical Spaces Using Geometric HashingJournal of Chemical Information and Modeling, 2005
- Randomized algorithms and NLPPublished by Association for Computational Linguistics (ACL) ,2005
- Similarity estimation techniques from rounding algorithmsPublished by Association for Computing Machinery (ACM) ,2002
- Efficient large-scale sequence comparison by locality-sensitive hashingBioinformatics, 2001
- Finding motifs using random projectionsPublished by Association for Computing Machinery (ACM) ,2001
- Min-Wise Independent PermutationsJournal of Computer and System Sciences, 2000
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- The Light Bulb ProblemInformation and Computation, 1995
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975