The DOI matches its Crossref record; 31 of the 31 references it cites were found in a registry or an index.
A simple algorithm for nearest neighbor search in high dimensions
Abstract
The problem of finding the closest point in high-dimensional spaces is common in pattern recognition. Unfortunately, the complexity of most existing search algorithms, such as k-d tree and R-tree, grows exponentially with dimension, making them impractical for dimensionality above 15. In nearly all applications, the closest point is of interest only if it lies within a user-specified distance /spl epsiv/. We present a simple and practical algorithm to efficiently search for the nearest neighbor within Euclidean distance /spl epsiv/. The use of projection search combined with a novel data structure dramatically improves performance in high dimensions. A complexity analysis is presented which helps to automatically determine /spl epsiv/ in structured problems. A comprehensive set of benchmarks clearly shows the superiority of the proposed algorithm for a variety of structured and unstructured search problems. Object recognition is demonstrated as an example application. The simplicity of the algorithm makes it possible to construct an inexpensive hardware search engine which can be 100 times faster than its software equivalent. A C++ implementation of our algorithm is available.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403
Multidimensional binary search trees used for associative searching
Bentley, J. L. (1975) · Communications of the ACM · doi:10.1145/361002.361007 · Cited by 7,520
R-trees: a dynamic index structure for spatial searching
Guttman, A. (1984) · Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84 · doi:10.1145/602259.602266 · Cited by 6,580
Voronoi diagrams—a survey of a fundamental geometric data structure
Aurenhammer, F. (1991) · ACM Computing Surveys · doi:10.1145/116873.116880 · Cited by 4,340
Computational Geometry--An Introduction.
Atallah, M. J., Preparata, F. P., & Shamos, M. I. (1986) · Mathematics of Computation · doi:10.2307/2008200 · Cited by 4,238
The R*-tree: an efficient and robust access method for points and rectangles
Beckmann, N., Kriegel, H.-P., Schneider, R., & Seeger, B. (1990) · Proceedings of the 1990 ACM SIGMOD international conference on Management of data · doi:10.1145/93597.98741 · Cited by 4,161
The Art of Computer Programming: Volume 3: Sorting and Searching
Knuth, D. E. (1973) · Cited by 3,955
An Algorithm for Finding Best Matches in Logarithmic Expected Time
Friedman, J. H., Bentley, J. L., & Finkel, R. A. (1977) · ACM Transactions on Mathematical Software · doi:10.1145/355744.355745 · Cited by 2,813
Visual learning and recognition of 3-d objects from appearance
Murase, H., & Nayar, S. K. (1995) · International Journal of Computer Vision · doi:10.1007/bf01421486 · Cited by 1,881
Self-citationAlgorithms in Combinatorial Geometry.
Goodman, J. E., & Edelsbrunner, H. (1989) · The American Mathematical Monthly · doi:10.2307/2325168 · Cited by 1,788
Knuth, D. E. (1973) · Cumulative Index of Computer Aided Architectural Design · Cited by 1,719
Algorithms in Combinatorial Geometry
Edelsbrunner, H. (1987) · Springer eBooks · doi:10.1007/978-3-642-61568-9 · Cited by 1,534
(1993) · doi:10.5555/313559.313789 · Cited by 998
The K-D-B-tree: a search structure for large multidimensional dynamic indexes
Robinson, J. T. (1981) · Proceedings of the 1981 ACM SIGMOD international conference on Management of data - SIGMOD '81 · doi:10.1145/582318.582321 · Cited by 888
A Branch and Bound Algorithm for Computing k-Nearest Neighbors
Fukunaga, K., & Narendra, P. M. (1975) · IEEE Transactions on Computers · doi:10.1109/t-c.1975.224297 · Cited by 736
Multidimensional divide-and-conquer
Bentley, J. L. (1980) · Communications of the ACM · doi:10.1145/358841.358850 · Cited by 672
Multidimensional Binary Search Trees in Database Applications
Bentley, J. L. (1979) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1979.234200 · Cited by 410
An Algorithm for Finding Nearest Neighbors
Friedman, J. H., Baskett, F., & Shustek, L. J. (1975) · IEEE Transactions on Computers · doi:10.1109/t-c.1975.224110 · Cited by 394
Refinements to nearest-neighbor searching ink-dimensional trees
Sproull, R. F. (1991) · Algorithmica · doi:10.1007/bf01759061 · Cited by 349
Sequencing-by-hybridization revisited: the analog-spectrum proposal
Preparata, F. P. (2004) · IEEE/ACM Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2004.12 · Cited by 320
Optimal Expected-Time Algorithms for Closest Point Problems
Bentley, J. L., Weide, B. W., & Yao, A. C.-C. (1980) · ACM Transactions on Mathematical Software · doi:10.1145/355921.355927 · Cited by 314
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
Netravali, A. N., & Haskell, B. G. (1995) · Springer eBooks · doi:10.1007/978-1-4899-6950-7 · Cited by 227
The K-D-B-tree: a search structure for large multidimensional dynamic indexes
Robinson, J. T. (1981) · Proceedings of the 1981 ACM SIGMOD international conference on Management of data - SIGMOD '81 · doi:10.1145/582319.582321 · Cited by 212
Real-time 100 object recognition system
Nayar, S. K., Nene, S. A., & Murase, H. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1996.506510 · Cited by 158
Self-citationOn the complexity ofd- dimensional Voronoi diagrams
Klee, V. L. (1980) · Archiv der Mathematik · doi:10.1007/bf01224932 · Cited by 111
Learning, positioning, and tracking visual appearance
Nayar, S. K., Murase, H., & Nene, S. A. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1994.351072 · Cited by 99
Self-citationNayar, S. K., Baker, S., & Murase, H. (1996) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.1996.517114 · Cited by 74
Self-citationA Technique to Identify Nearest Neighbors
Yunck, T. P. (1976) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1976.4309418 · Cited by 74
Nearest neighbor searching and applications
Arya, S. (1996) · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · Cited by 41
Cited by
Example-based super-resolution
Freeman, W. T., Jones, T. R., & Pasztor, E. C. (2002) · IEEE Computer Graphics and Applications · doi:10.1109/38.988747 · Cited by 2,498
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
Image Alignment and Stitching: A Tutorial
Szeliski, R. (2007) · Foundations and Trends in Computer Graphics and Vision · doi:10.1561/0600000009 · Cited by 1,593
Fast texture synthesis using tree-structured vector quantization
Wei, L.-Y., & Levoy, M. (2000) · Proceedings of the 27th annual conference on Computer graphics and interactive techniques - SIGGRAPH '00 · doi:10.1145/344779.345009 · Cited by 1,356
Chávez, E., Navarro, G., Baeza-Yates, R., & Marroquín, J. L. (2001) · ACM Computing Surveys · doi:10.1145/502807.502808 · Cited by 1,246
Metadata
- Authors
- Nene, S. A., & Nayar, S. K.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 1997
- Volume
- 19
- Issue
- 9
- Pages
- 989-1003
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2129287653
- Cited by
- 311
- References
- 31
- FWCI
- 9.71
- Type
- journal article
- 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.