The DOI matches its Crossref record; 38 of the 38 references it cites were found in a registry or an index.
Efficient search for approximate nearest neighbor in high dimensional spaces
Open accessAbstract
We address the problem of designing data structures that allow efficient search for approximate nearest neighbors.More specifically, given a database consisting of a set of vectors in some high dimensional Euclidean space, we want to construct a space-efficient data struct,ure t,hat would allow us to search, given a query vector, for t.he closest or nearly closest vector in the database.We also address t.hii problem when distances are measured by the L1 norm, and in t.he Hamming cube.Sign%cant.lyimproving and extending recent results of Kleinberg, we const,ruct data structures whose size is polynomial in the size of t,he database, and search algorithms t,hat run in time nearly linear or nearly quadratic in the dimension (depending on the case; the extra factors are polylogarit.hmicin the size of the database).
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
Nearest neighbor pattern classification
Cover, T., & Hart, P. (1967) · IEEE Transactions on Information Theory · doi:10.1109/tit.1967.1053964 · Cited by 16,936
(1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 12,895
Indexing by latent semantic analysis
Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K., & Harshman, R. (1990) · Journal of the American Society for Information Science · doi:10.1002/(sici)1097-4571(199009)41:6<391::aid-asi1>3.0.co;2-9 · Cited by 12,751
Vector Quantization and Signal Compression
Gersho, A., & Gray, R. M. (1992) · Springer eBooks · doi:10.1007/978-1-4615-3626-0 · Cited by 7,003
Pattern Classification and Scene Analysis
Thompson, M., Duda, R. O., & Hart, P. E. (1974) · Leonardo · doi:10.2307/1573081 · Cited by 4,495
Spencer, J. (1991) · Medical Entomology and Zoology · Cited by 4,310
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
Pattern classification and scene analysis
Chien, Y. (1974) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1974.1100577 · Cited by 3,398
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (2015) · Measures of Complexity · doi:10.1007/978-3-319-21852-6_3 · Cited by 3,105
Query by image and video content: the QBIC system
Flickner, M., Sawhney, H., Niblack, W., Ashley, J., Huang, Q., Dom, B., Gorkani, M., Hafner, J., Lee, D., Petkovic, D., et al. (1995) · Computer · doi:10.1109/2.410146 · Cited by 3,060
Extensions of Lipschitz mappings into a Hilbert space
Johnson, W. B., & Lindenstrauss, J. (1984) · Contemporary Mathematics · doi:10.1090/conm/026/737400 · Cited by 2,523
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (1971) · Theory of Probability & Its Applications · doi:10.1137/1116025 · Cited by 2,448
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998) · Journal of the ACM · doi:10.1145/293347.293348 · Cited by 2,300
(2005) · Complexity Theory · doi:10.1007/3-540-27477-4_15 · Cited by 1,629
Salton, G. (1988) · Cited by 1,587
Photobook: Content-based manipulation of image databases
Pentland, A., Picard, R. W., & Sclaroff, S. (1996) · International Journal of Computer Vision · doi:10.1007/bf00123143 · Cited by 1,562
Query by Image and Video Content: The QBIC System
Flickner, M., Sawhney, H., Niblack, W., Ashley, J., Huang, Q., Dom, B., Gorkani, M., Hafner, J., Lee, D., Petkovic, D., et al. (2002) · Readings in Multimedia Computing and Networking · doi:10.1016/b978-155860651-7/50108-x · Cited by 1,559
A hard-core predicate for all one-way functions
Goldreich, O., & Levin, L. A. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73010 · Cited by 1,193
The geometry of graphs and some of its algorithmic applications
Linial, N., London, E., & Rabinovich, Y. (1995) · Combinatorica · doi:10.1007/bf01200757 · Cited by 952
Shape indexing using approximate nearest-neighbour search in high-dimensional spaces
Beis, J. S., & Lowe, D. G. (2002) · Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.1997.609451 · Cited by 879
Photobook: tools for content-based manipulation of image databases:
Pentland, A. P., Picard, R. W., & Scarloff, S. (1994) · SPIE Proceedings · doi:10.1117/12.171786 · Cited by 879
Discriminant adaptive nearest neighbor classification
Hastie, T., & Tibshirani, R. (1996) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.506411 · Cited by 833
A weighted nearest neighbor algorithm for learning with symbolic features
Cost, S., & Salzberg, S. (1993) · Machine Learning · doi:10.1007/bf00993481 · Cited by 764
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
Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality
Indyk, P., & Motwani, R. (1998) · Cited by 486
The dimension of almost spherical sections of convex bodies
Figiel, T., Lindenstrauss, J., & Milman, V. D. (1977) · Acta Mathematica · doi:10.1007/bf02392234 · Cited by 401
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
A Randomized Algorithm for Closest-Point Queries
Clarkson, K. L. (1988) · SIAM Journal on Computing · doi:10.1137/0217052 · Cited by 248
Multidimensional Searching Problems
Dobkin, D., & Lipton, R. J. (1976) · SIAM Journal on Computing · doi:10.1137/0205015 · Cited by 248
Reporting points in halfspaces
Matous̆ek, J. (1992) · Computational Geometry · doi:10.1016/0925-7721(92)90006-e · Cited by 233
The geometry of graphs and some of its algorithmic applications
Linial, N., London, E., & Rabinovich, Y. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365733 · Cited by 190
Locality-preserving hashing in multidimensional spaces
Indyk, P., Motwani, R., Raghavan, P., & Vempala, S. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258656 · Cited by 167
Point Location in Arrangements of Hyperplanes
Meiser, S. (1993) · Information and Computation · doi:10.1006/inco.1993.1057 · Cited by 154
A general approach to d-dimensional geometric queries
Yao, A. C.-C., & Yao, F. F. (1985) · doi:10.1145/22145.22163 · Cited by 144
An algorithm for approximate closest-point queries
Clarkson, K. L. (1994) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/177424.177609 · Cited by 133
8 Nearest neighbor methods in discrimination
Devroye, L., & Wagner, T. J. (1982) · Handbook of statistics · doi:10.1016/s0169-7161(82)02011-2 · Cited by 102
Finding the neighborhood of a query in a dictionary
Dolev, D., Harari, Y., & Parnas, M. (2002) · doi:10.1109/istcs.1993.253486 · Cited by 20
Neighborhood preserving hashing and approximate queries
Dolev, D., Harari, Y. N., Linial, N., Nisan, N., & Parnas, M. (1994) · Symposium on Discrete Algorithms · doi:10.5555/314464.314501 · Cited by 18
Cited by
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
Locality-sensitive hashing scheme based on p-stable distributions
Datar, M., Immorlica, N., Indyk, P., & Mirrokni, V. S. (2004) · Proceedings of the twentieth annual symposium on Computational geometry · doi:10.1145/997817.997857 · Cited by 2,936
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998) · Journal of the ACM · doi:10.1145/293347.293348 · Cited by 2,300
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Andoni, A., & Indyk, P. (2008) · Communications of the ACM · doi:10.1145/1327452.1327494 · Cited by 1,437
“The algorithms of [25, 21] use onlyoneprobe.”
BackgroundNear-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
Andoni, A., & Indyk, P. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.49 · Cited by 1,067
Metadata
- Authors
- Kushilevitz, E., Ostrovsky, R., & Rabani, Y.
- Venue
- Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98
- Publisher
- ACM Press
- Published
- 1998
- Pages
- 614-623
- OpenAlex
- W2050749090
- Cited by
- 259
- References
- 38
- FWCI
- 23.19
- Type
- conference paper
- Language
- en
- Open access
- gold
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.