The DOI matches its Crossref record; 63 of the 63 references it cites were found in a registry or an index.
Scalable Nearest Neighbor Algorithms for High Dimensional Data
Open accessAbstract
For many computer vision and machine learning problems, large training sets are key for good performance. However, the most computationally expensive part of many computer vision and machine learning algorithms consists of finding nearest neighbor matches to high dimensional vectors that represent the training data. We propose new algorithms for approximate nearest neighbor matching and evaluate and compare them with previous algorithms. For matching high dimensional features, we find two algorithms to be the most efficient: the randomized k-d forest and a new algorithm proposed in this paper, the priority search k-means tree. We also propose a new algorithm for matching binary features by searching multiple hierarchical clustering trees and show it outperforms methods typically used in the literature. We show that the optimal nearest neighbor algorithm and its parameters depend on the data set characteristics and describe an automated configuration procedure for finding the best algorithm to search a particular data set. In order to scale to very large data sets that would otherwise not fit in the memory of a single machine, we propose a distributed nearest neighbor matching framework that can be used with any of the algorithms described in the paper. All this research has been released as an open source library called fast library for approximate nearest neighbors (FLANN), which has been incorporated into OpenCV and is now one of the most popular libraries for nearest neighbor matching.
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
ImageNet: A large-scale hierarchical image database
Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., & Fei-Fei, L. (2009) · 2009 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2009.5206848 · Cited by 65,333
Distinctive Image Features from Scale-Invariant Keypoints
Lowe, D. G. (2004) · International Journal of Computer Vision · doi:10.1023/b:visi.0000029664.99615.94 · Cited by 55,589
Self-citationA Simplex Method for Function Minimization
Nelder, J. A., & Mead, R. (1965) · The Computer Journal · doi:10.1093/comjnl/7.4.308 · Cited by 28,905
ORB: An efficient alternative to SIFT or SURF
Rublee, E., Rabaud, V., Konolige, K., & Bradski, G. (2011) · 2011 International Conference on Computer Vision · doi:10.1109/iccv.2011.6126544 · Cited by 11,037
ROS: an open-source Robot Operating System
Quigley, M. (2009) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · Cited by 8,729
(2012) · Cited by 8,009
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
(2007) · doi:10.5555/1283383.1283494 · Cited by 7,364
Video Google: a text retrieval approach to object matching in videos
Sivic, & Zisserman (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238663 · Cited by 6,367
BRIEF: Binary Robust Independent Elementary Features
Calonder, M., Lepetit, V., Strecha, C., & Fua, P. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-15561-1_56 · Cited by 3,597
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
BRISK: Binary Robust invariant scalable keypoints
Leutenegger, S., Chli, M., & Siegwart, R. Y. (2011) · 2011 International Conference on Computer Vision · doi:10.1109/iccv.2011.6126542 · Cited by 3,450
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 · cited 2×
“Dimensionality reduction has been used in the literature with good results ([7], [27], [28], [32], [57]), however even with dimensionality reduction it can be challenging to fit the data in the memory of a single machine for very large data sets.”
BackgroundMethodObject retrieval with large vocabularies and fast spatial matching
Philbin, J., Chum, O., Isard, M., Sivic, J., & Zisserman, A. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383172 · Cited by 2,929
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
FAST APPROXIMATE NEAREST NEIGHBORS WITH AUTOMATIC ALGORITHM CONFIGURATION
(2009) · Proceedings of the Fourth International Conference on Computer Vision Theory and Applications · doi:10.5220/0001787803310340 · Cited by 2,640
Learning openCV: computer vision with the openCV library
Bradski, G. R., & Kaehler, A. (2008) · CERN Document Server (European Organization for Nuclear Research) · Cited by 2,468
Weiss, Y., Torralba, A. B., & Fergus, R. (2008) · neural information processing systems · Cited by 2,389
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
80 Million Tiny Images: A Large Data Set for Nonparametric Object and Scene Recognition
Torralba, A., Fergus, R., & Freeman, W. T. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.128 · Cited by 1,921
The Unreasonable Effectiveness of Data
Halevy, A., Norvig, P., & Pereira, F. (2009) · IEEE Intelligent Systems · doi:10.1109/mis.2009.36 · Cited by 1,767
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
(1993) · doi:10.5555/313559.313789 · Cited by 998
Kernelized locality-sensitive hashing for scalable image search
Kulis, B., & Grauman, K. (2009) · 2009 IEEE 12th International Conference on Computer Vision · doi:10.1109/iccv.2009.5459466 · Cited by 890
ParamILS: An Automatic Algorithm Configuration Framework
Hutter, F., Hoos, H. H., Leyton-Brown, K., & Stuetzle, T. (2009) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2861 · Cited by 882
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
Self-citationIM2GPS: estimating geographic information from a single image
Hays, J., & Efros, A. A. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587784 · Cited by 877
Shape Matching and Object Recognition Using Low Distortion Correspondences
Berg, A. C., Berg, T. L., & Malik, J. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.320 · Cited by 845
Cover trees for nearest neighbor
Beygelzimer, A., Kakade, S., & Langford, J. (2006) · Proceedings of the 23rd international conference on Machine learning - ICML '06 · doi:10.1145/1143844.1143857 · Cited by 813
Learning to Hash with Binary Reconstructive Embeddings
Kulis, B., & Darrell, T. (2009) · Cited by 806
Fast pose estimation with parameter-sensitive hashing
Shakhnarovich, Viola, & Darrell (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238424 · Cited by 758
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
Small codes and large image databases for recognition
Torralba, A., Fergus, R., & Weiss, Y. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587633 · Cited by 727
Scene completion using millions of photographs
Hays, J., & Efros, A. A. (2007) · ACM SIGGRAPH 2007 papers · doi:10.1145/1275808.1276382 · Cited by 687
Optimised KD-trees for fast image descriptor matching
Silpa-Anan, C., & Hartley, R. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587638 · Cited by 677
Multi-probe LSH: efficient indexing for high-dimensional similarity search
Lv, Q., Josephson, W. K., Wang, Z., Charikar, M., & Li, K. (2007) · Very Large Data Bases · Cited by 634
City-Scale Location Recognition
Schindler, G., Brown, M., & Szeliski, R. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383150 · Cited by 626
Semi-supervised hashing for scalable image retrieval
Wang, J., Kumar, S., & Chang, S.-F. (2010) · 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2010.5539994 · Cited by 601
Locality-sensitive binary codes from shift-invariant kernels
Raginsky, M., & Lazebnik, S. (2009) · Cited by 600
Near Neighbor Search in Large Metric Spaces
Brin, S. (1995) · Cited by 556
Scene completion using millions of photographs
Hays, J., & Efros, A. A. (2007) · ACM Transactions on Graphics · doi:10.1145/1276377.1276382 · Cited by 534
Random projection trees and low dimensional manifolds
Dasgupta, S., & Freund, Y. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374452 · Cited by 375
LSH forest: self-tuning indexes for similarity search
Bawa, M., Condie, T., & Ganesan, P. (2005) · Proceedings of the 14th international conference on World Wide Web - WWW '05 · doi:10.1145/1060745.1060840 · Cited by 353
Refinements to nearest-neighbor searching ink-dimensional trees
Sproull, R. F. (1991) · Algorithmica · doi:10.1007/bf01759061 · Cited by 349
Learning Local Image Descriptors
Winder, S. A. J., & Brown, M. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.382971 · Cited by 339
Fast Matching of Binary Features
Muja, M., & Lowe, D. G. (2012) · 2012 Ninth Conference on Computer and Robot Vision · doi:10.1109/crv.2012.60 · Cited by 297
Self-citationHighly scalable appearance-only SLAM - FAB-MAP 2.0
Cummins, M., & Newman, P. (2009) · Robotics: Science and Systems V · doi:10.15607/rss.2009.v.039 · Cited by 282
Fast image search for learned metrics
Jain, P., Kulis, B., & Grauman, K. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587841 · Cited by 279
Turcot, P., & Lowe, D. G. (2009) · 2009 IEEE 12th International Conference on Computer Vision Workshops, ICCV Workshops · doi:10.1109/iccvw.2009.5457541 · Cited by 235
Self-citationBabenko, A., & Lempitsky, V. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6248038 · Cited by 200
Complementary hashing for approximate nearest neighbor search
Xu, H., Wang, J., Li, Z., Zeng, G., Li, S., & Yu, N. (2011) · 2011 International Conference on Computer Vision · doi:10.1109/iccv.2011.6126424 · Cited by 162
The Anchors Hierarchy: Using the Triangle Inequality to Survive High Dimensional Data
Moore, A. (2000) · Cited by 152
Scalable similarity search with optimized kernel hashing
He, J., Liu, W., & Chang, S. (2010) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1835804.1835946 · Cited by 151
Scalable k-NN graph construction for visual descriptors
Wang, J., Wang, J., Zeng, G., Tu, Z., Gan, R., & Li, S. (2012) · 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.2012.6247790 · Cited by 146
Improving Descriptors for Fast Tree Matching by Optimal Linear Projection
Mikolajczyk, K., & Matas, J. (2007) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2007.4408871 · Cited by 94
Efficient Clustering and Matching for Object Class Recognition
Leibe, B., Mikolajczyk, K., & Schiele, B. (2006) · British Machine Vision Conference (BMVC) · doi:10.5244/c.20.81 · Cited by 92
Automated configuration of algorithms for solving hard computational problems
Hutter, F. (2009) · cIRcle (University of British Columbia) · doi:10.14288/1.0051652 · Cited by 84
Randomized structure from motion based on atomic 3D models from camera triplets
Havlena, M., Torii, A., Knopp, J., & Pajdla, T. (2009) · 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.2009.5206677 · Cited by 65
Optimizing kd-trees for scalable visual descriptor indexing
Jia, Y., Wang, J., Zeng, G., Zha, H., & Hua, X. (2010) · 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.2010.5540006 · Cited by 64
Metric-based shape retrieval in large databases
Sebastian, T. B., & Kimia, B. B. (2003) · Object recognition supported by user interaction for service robots · doi:10.1109/icpr.2002.1047852 · Cited by 58
Distributed Kd-Trees for Retrieval from Very Large Image Collections
Aly, M., Munich, M. E., & Perona, P. (2011) · Cited by 56
The 30th Anniversary of the IEEE Transactions on Pattern Analysis and Machine Intelligence
Zabih, R. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.8 · Cited by 36
Automatic Reconstruction of Mars Artifacts
Havlena, M., Torii, A., Jančošek, M., & Pajdla, T. (2009) · European Planetary Science Congress 2009 · Cited by 2
Cited by
Malkov, Y. A., & Yashunin, D. A. (2020) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2018.2889473 · Cited by 1,904
Graph-based approach for airborne light detection and ranging segmentation
Vilariño, D. L., Cabaleiro, J. C., Martínez, J., Rivera, F. F., & Pena, T. F. (2017) · Journal of Applied Remote Sensing · doi:10.1117/1.jrs.11.015020 · Cited by 1,721
D2-Net: A Trainable CNN for Joint Description and Detection of Local Features
Dusmanu, M., Rocco, I., Pajdla, T., Pollefeys, M., Sivic, J., Torii, A., & Sattler, T. (2019) · 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2019.00828 · Cited by 1,179
Open3D: A Modern Library for 3D Data Processing
Zhou, Q.-Y., Park, J., & Koltun, V. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1801.09847 · Cited by 1,124
Big IoT data analytics: Architecture, opportunities, and open research challenges
(2017) · IEEE Access · doi:10.1109/access.2017.2689040 · Cited by 980
Metadata
- Authors
- Muja, M., & Lowe, D. G.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2014-11-01
- Volume
- 36
- Issue
- 11
- Pages
- 2227-2240
- ISSN
- 0162-8828 (ISSN-L)
- 2160-9292
- OpenAlex
- W2086504823
- Cited by
- 1,407
- References
- 63
- FWCI
- 122.55
- Type
- journal article
- Language
- en
- Open access
- bronze
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.