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
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
Wang, J., Zhang, T., Song, J., Sebe, N., & Shen, H. T. (2018) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2699960 · Cited by 971
Deciphering interaction fingerprints from protein molecular surfaces using geometric deep learning
Gainza, P., Sverrisson, F., Monti, F., Rodolà, E., Boscaini, D., Bronstein, M. M., & Correia, B. E. (2020) · Nature Methods · doi:10.1038/s41592-019-0666-6 · Cited by 834
Pose estimation for augmented reality: a hands-on survey
Marchand, E., Uchiyama, H., & Spindler, F. (2016) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2015.2513408 · Cited by 746
SIFT Meets CNN: A Decade Survey of Instance Retrieval
Zheng, L., Yang, Y., & Tian, Q. (2018) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2709749 · Cited by 752
GMS: Grid-Based Motion Statistics for Fast, Ultra-Robust Feature Correspondence
Bian, J., Lin, W.-Y., Matsushita, Y., Yeung, S.-K., Nguyen, T.-D., & Cheng, M.-M. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.302 · Cited by 594
Douze, M., Guzhva, A., Deng, C., Johnson, J., Szilvasy, G., Mazaré, P.-E., Lomeli, M., Hosseini, L., & Jégou, H. (2026) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2025.3618474 · Cited by 478
Li, W., Zhang, Y., Sun, Y., Wang, W., Li, M., Zhang, W., & Lin, X. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2909204 · Cited by 454
Deep learning for accelerated all-dielectric metasurface design
Nadell, C. C., Huang, B., Malof, J. M., & Padilla, W. J. (2019) · Optics Express · doi:10.1364/oe.27.027523 · Cited by 450
(2021) · doi:10.1145/3448016.3457550 · Cited by 416
Learning visual similarity for product design with convolutional neural networks
Bell, S., & Bala, K. (2015) · ACM Transactions on Graphics · doi:10.1145/2766959 · Cited by 408
Hough-CNN: Deep learning for segmentation of deep brain regions in MRI and ultrasound
Milletari, F., Ahmadi, S.-A., Kroll, C., Plate, A., Rozanski, V., Maiostre, J., Levin, J., Dietrich, O., Ertl-Wagner, B., Bötzel, K., et al. (2017) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2017.04.002 · Cited by 391
Learning descriptors for object recognition and 3D pose estimation
Wohlhart, P., & Lepetit, V. (2015) · 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2015.7298930 · Cited by 358
Estimating the intrinsic dimension of datasets by a minimal neighborhood information
Facco, E., d’Errico, M., Rodriguez, A., & Laio, A. (2017) · Scientific Reports · doi:10.1038/s41598-017-11873-y · Cited by 351
A review of 3D reconstruction techniques in civil engineering and their applications
Ma, Z., & Liu, S. (2018) · Advanced Engineering Informatics · doi:10.1016/j.aei.2018.05.005 · Cited by 347
Granular ball computing classifiers for efficient, scalable and robust learning
Xia, S., Liu, Y., Ding, X., Wang, G., Yu, H., & Luo, Y. (2019) · Information Sciences · doi:10.1016/j.ins.2019.01.010 · Cited by 341
Segmentation-Driven 6D Object Pose Estimation
Hu, Y., Hugonot, J., Fua, P., & Salzmann, M. (2019) · 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2019.00350 · Cited by 333
Outlier Detection: Methods, Models, and Classification
Boukerche, A., Zheng, L., & Alfandi, O. (2021) · ACM Computing Surveys · doi:10.1145/3381028 · Cited by 334
Approximated and User Steerable tSNE for Progressive Visual Analytics
Pezzotti, N., Lelieveldt, B. P. F., Maaten, L. V. D., Hollt, T., Eisemann, E., & Vilanova, A. (2017) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2016.2570755 · Cited by 308
Deep Learning of Local RGB-D Patches for 3D Object Detection and 6D Pose Estimation
Kehl, W., Milletari, F., Tombari, F., Ilic, S., & Navab, N. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-46487-9_13 · Cited by 283
GSPBOX: A toolbox for signal processing on graphs
Perraudin, N., Paratte, J., Shuman, D. I., Martin, L., Kalofolias, V., Vandergheynst, P., & Hammond, D. K. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1408.5781 · Cited by 268
Jointly Optimizing Query Encoder and Product Quantization to Improve Retrieval Performance
Zhan, J., Mao, J., Liu, Y., Guo, J., Zhang, M., & Ma, S. (2021) · Proceedings of the 30th ACM International Conference on Information & Knowledge Management · doi:10.1145/3459637.3482358 · Cited by 91
Scaling Memory-Augmented Neural Networks with Sparse Reads and Writes
Rae, J. W., Hunt, J. J., Harley, T., Danihelka, I., Senior, A., Wayne, G., Graves, A., & Lillicrap, T. P. (2016) · arXiv · doi:10.48550/arxiv.1610.09027 · Cited by 89
Is Geometry Enough for Matching in Visual Localization?
Zhou, Q., Agostinho, S., Osep, A., & Leal-Taixé, L. (2022) · arXiv · doi:10.48550/arxiv.2203.12979 · Cited by 52
Off the Beaten Path: Let's Replace Term-Based Retrieval with k-NN Search
Boytsov, L., Novak, D., Malkov, Y., & Nyberg, E. (2016) · Proceedings of the 25th ACM International on Conference on Information and Knowledge Management · doi:10.1145/2983323.2983815 · Cited by 50
Semantic labeling for prosthetic vision
Horne, L., Alvarez, J., McCarthy, C., Salzmann, M., & Barnes, N. (2016) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2016.02.015 · Cited by 30
Deep multimodal embedding: Manipulating novel objects with point-clouds, language and trajectories
Sung, J., Lenz, I., & Saxena, A. (2017) · 2017 IEEE International Conference on Robotics and Automation (ICRA) · doi:10.1109/icra.2017.7989325 · Cited by 26
Illumination invariant feature point matching for high-resolution planetary remote sensing images
Wu, B., Zeng, H., & Hu, H. (2018) · Planetary and Space Science · doi:10.1016/j.pss.2018.01.007 · Cited by 20
Steger, C. (2017) · Handbook of Machine and Computer Vision · doi:10.1002/9783527413409.ch9 · Cited by 6
A Biresolution Spectral Framework for Product Quantization
Mukherjee, L., Peng, J., Ravi, S. N., & Singh, V. (2018) · 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2018.00351 · Cited by 2
Kang, G., Ge, Z., Hu, J., Zhang, X., Wang, L., & Zhan, J. (2025) · Proceedings of the VLDB Endowment · doi:10.14778/3718057.3718078 · Cited by 1
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.