The DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Locality-sensitive hashing scheme based on p-stable distributions
Abstract
We present a novel Locality-Sensitive Hashing scheme for the Approximate Nearest Neighbor Problem under lp norm, based on p-stable distributions.Our scheme improves the running time of the earlier algorithm for the case of the lp norm. It also yields the first known provably efficient approximate NN algorithm for the case p<1. We also show that the algorithm finds the exact near neigbhor in O(log n) time for data satisfying certain "bounded growth" condition.Unlike earlier schemes, our LSH scheme works directly on points in the Euclidean space without embeddings. Consequently, the resulting query time bound is free of large factors and is simple and easy to implement. Our experiments (on synthetic data sets) show that the our data structure is up to 40 times faster than kd-tree.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
Self-citation(1999) · Cited by 3,186
When Is ''Nearest Neighbor'' Meaningful?
Beyer, K., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49257-7_15 · Cited by 2,403 · cited 1×
“In fact, in situations when the quality of the approx imate nearest neighbor is much worse than the quality of the actual nearest neighbor, then the nearest neighbor problem is unstable, and it is not clear if solving it is at all meaningful [4, 17].”
BackgroundOn the Surprising Behavior of Distance Metrics in High Dimensional Space
Aggarwal, C. C., Hinneburg, A., & Keim, D. A. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44503-x_27 · Cited by 2,083
One-Dimensional Stable Distributions
Zolotarev, V. (1986) · Translations of Mathematical Monographs · doi:10.1090/mmono/065 · Cited by 1,843
An optimal algorithm for approximate nearest neighbor searching
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1994) · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · doi:10.5555/314464.314652 · Cited by 594
Finding Motifs Using Random Projections
Buhler, J., & Tompa, M. (2002) · Journal of Computational Biology · doi:10.1089/10665270252935430 · Cited by 532
What Is the Nearest Neighbor in High Dimensional Spaces
Hinneburg, A., Aggarwal, C. C., & Keim, D. A. (2000) · KOPS (University of Konstanz) · Cited by 505
Mean shift based clustering in high dimensions: a texture classification example
Georgescu, Shimshoni, & Meer (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238382 · Cited by 412
Two algorithms for nearest-neighbor search in high dimensions
Kleinberg, J. M. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258653 · Cited by 348
Finding interesting associations without support pruning
Cohen, E., Datar, M., Fujiwara, S., Gionis, A., Indyk, P., Motwani, R., Ullman, J. D., & Yang, C. (2001) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.908981 · Cited by 341
Self-citationFinding nearest neighbors in growth-restricted metrics
Karger, D. R., & Ruhl, M. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.510013 · Cited by 334
Navigating nets: simple algorithms for proximity search
Krauthgamer, R., & Lee, J. R. (2015) · Cited by 308
Efficient search for approximate nearest neighbor in high dimensional spaces
Kushilevitz, E., Ostrovsky, R., & Rabani, Y. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276877 · Cited by 259
Efficient large-scale sequence comparison by locality-sensitive hashing
Buhler, J. (2001) · Bioinformatics · doi:10.1093/bioinformatics/17.5.419 · Cited by 259
Stable distributions, pseudorandom generators, embeddings and data stream computation
Indyk, P. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892082 · Cited by 238
Self-citationANN: library for approximate nearest neighbor searching
Arya, S., & Mount, D. M. (1998) · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · Cited by 209
Finding motifs using random projections
Buhler, J., & Tompa, M. (2001) · Proceedings of the fifth annual international conference on Computational biology · doi:10.1145/369133.369172 · Cited by 165
Scalable Techniques for Clustering the Web.
Haveliwala, T. H., Gionis, A., & Indyk, P. (2000) · Cited by 148
Self-citationA replacement for Voronoi diagrams of near linear size
Har-Peled, S. (2001) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959884 · Cited by 147
Nearest neighbor queries in metric spaces
Clarkson, K. L. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258655 · Cited by 59
Cluster-based delta compression of a collection of files
Ouyang, Z., Memon, N. D., Suel, T., & Trendafilov, D. (2003) · International Conference on Web Information Systems Engineering (WISE) · doi:10.1109/wise.2002.1181662 · Cited by 50
MACS: music audio characteristic sequence indexing for similarity retrieval
Yang, C. (2002) · IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (WASPAA) · doi:10.1109/aspaa.2001.969558 · Cited by 42
Fast mining of massive tabular data via approximate distance computations
Cormode, G., Indyk, P., Koudas, N., & Muthukrishnan, S. (2003) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2002.994778 · Cited by 36
Self-citationLocally lifting the curse of dimensionality for nearest neighbor search
Yianilos, P. N. (2002) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/059/08 · Cited by 33
Locally lifting the curse of dimensionality for nearest neighbor search (extended abstract)
Yianilos, P. N. (2000) · doi:10.5555/338219.338273 · Cited by 26
Cited by
Deep learning in neural networks: an overview
Schmidhuber, J. (2015) · Neural Networks · doi:10.1016/j.neunet.2014.09.003 · Cited by 18,570
Speeded-Up Robust Features (SURF)
Bay, H., Ess, A., Tuytelaars, T., & Van Gool, L. (2008) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2007.09.014 · Cited by 13,557
Scalable Recognition with a Vocabulary Tree
Nister, D., & Stewenius, H. (2006) · 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 2 (CVPR'06) · doi:10.1109/cvpr.2006.264 · Cited by 3,579
Product Quantization for Nearest Neighbor Search
Jégou, H., Douze, M., & Schmid, C. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.57 · Cited by 2,956
“In this case, one of the most popular ANN algorithms is the Euclidean Locality-Sensitive Hashing (E2LSH) [7], [11], which provides theoretical guarantees on the search quality with limited assumptions.”
BackgroundMethodInfluentialAggregating local descriptors into a compact image representation
Jegou, H., Douze, M., Schmid, C., & Perez, P. (2010) · 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2010.5540039 · Cited by 2,692
Metadata
- Authors
- Datar, M., Immorlica, N., Indyk, P., & Mirrokni, V. S.
- Venue
- Proceedings of the twentieth annual symposium on Computational geometry
- Publisher
- ACM
- Published
- 2004-06-08
- Pages
- 253-262
- OpenAlex
- W2162006472
- Cited by
- 2,936
- References
- 26
- FWCI
- 17.28
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.