The DOI matches its Crossref record; 33 of the 33 references it cites were found in a registry or an index.
Approximate nearest neighbor algorithm based on navigable small world graphs
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
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060
Nearest neighbor pattern classification
Cover, T., & Hart, P. (1967) · IEEE Transactions on Information Theory · doi:10.1109/tit.1967.1053964 · Cited by 16,936
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
Item-based collaborative filtering recommendation algorithms
Sarwar, B., Karypis, G., Konstan, J., & Riedl, J. (2001) · Proceedings of the 10th international conference on World Wide Web · doi:10.1145/371920.372071 · Cited by 9,135 · cited 2×
“…University Higher School of Economics, Laboratory of Algorithms and Technologies for Network Analysis, 136 Rodionova, Nizhny Novgorod 603093, Russia d Nizhny Novgorod State Technical University, Nizhny Novgorod, Russia a r t i c l e i n f o Keywords: Similarity search k-Nearest neighbor…”
BackgroundInfluentialMultidimensional binary search trees used for associative searching
Bentley, J. L. (1975) · Communications of the ACM · doi:10.1145/361002.361007 · Cited by 7,520
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
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
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
Quad trees a data structure for retrieval on composite keys
Finkel, R. A., & Bentley, J. L. (1974) · Acta Informatica · doi:10.1007/bf00288933 · Cited by 2,041
The small-world phenomenon: an algorithmic perspective
Kleinberg, J. (2000) · Proceedings of the thirty-second annual ACM symposium on Theory of computing · doi:10.1145/335305.335325 · Cited by 1,882
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
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality
Har-Peled, S., Indyk, P., & Motwani, R. (2012) · Theory of Computing · doi:10.4086/toc.2012.v008a014 · Cited by 816
A weighted nearest neighbor algorithm for learning with symbolic features
Cost, S., & Salzberg, S. (1993) · Machine Learning · doi:10.1007/bf00993481 · Cited by 764
Rychlik, W., & Rhoads, R. E. (1989) · Nucleic Acids Research · doi:10.1093/nar/17.21.8543 · Cited by 673
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 neighbor queries in fixed dimensions
Arya, S., & Mount, D. M. (1993) · doi:10.5555/313559.313768 · Cited by 303
Searching in metric spaces by spatial approximation
Navarro, G. (2002) · The VLDB Journal The International Journal on Very Large Data Bases · doi:10.1007/s007780200060 · Cited by 272
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
Lee, D. T., & Wong, C. K. (1977) · Acta Informatica · doi:10.1007/bf00263763 · Cited by 220
Query by Image and Video Content
Flickner, M. (1995) · Medical Entomology and Zoology · Cited by 198
Effective Proximity Retrieval by Ordering Permutations
Chavez, E., Figueroa, K., & Navarro, G. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.70815 · Cited by 179
Nearest Neighbor Queries in Metric Spaces
Clarkson, K. L. (1999) · Discrete & Computational Geometry · doi:10.1007/pl00009449 · Cited by 169
CoPhIR: a Test Collection for Content-Based Image RetrievalPreprint
Bolettieri, P., Esuli, A., Falchi, F., Lucchese, C., Perego, R., Piccioli, T., & Rabitti, F. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0905.4627 · Cited by 153
Fast Approximate Similarity Search in Extremely High-Dimensional Data Sets
Houle, M. E., & Sakuma, J. (2005) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2005.66 · Cited by 95
Distributed similarity search in high dimensions using locality sensitive hashing
Haghani, P., Michel, S., & Aberer, K. (2009) · International Conference on Extending Database Technology (EDBT) · doi:10.1145/1516360.1516446 · Cited by 89
Approximate similarity search: A multi-faceted problem
Patella, M., & Ciaccia, P. (2008) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2008.09.014 · Cited by 82
On nonmetric similarity search problems in complex domains
Skopal, T., & Bustos, B. (2011) · ACM Computing Surveys · doi:10.1145/1978802.1978813 · Cited by 76
Probabilistic proximity search: Fighting the curse of dimensionality in metric spaces
Chávez, E., & Navarro, G. (2002) · Information Processing Letters · doi:10.1016/s0020-0190(02)00344-7 · Cited by 54
VoroNet: A scalable object network based on Voronoi tessellations
Beaumont, O., Kermarrec, A.-M., Marchal, L., & Riviere, E. (2007) · 2007 IEEE International Parallel and Distributed Processing Symposium · doi:10.1109/ipdps.2007.370210 · Cited by 52
Malkov, Y. A., Ponomarenko, A., Logvinov, A., & Krylov, V. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32153-5_10 · Cited by 47
Self-citationSuccinct nearest neighbor search
Téllez, E. S., Chávez, E., & Navarro, G. (2011) · Similarity Search and Applications · doi:10.1145/1995412.1995420 · Cited by 30
Peer to Peer Multidimensional Overlays: Approximating Complex Structures
Beaumont, O., Kermarrec, A.-M., & Rivière, É. (2008) · Springer eBooks · doi:10.1007/978-3-540-77096-1_23 · Cited by 26
Navigating K-Nearest Neighbor Graphs to Solve Nearest Neighbor Searches
Chávez, E., & Téllez, E. S. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15992-3_29 · Cited by 14
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
Self-citationLi, 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
Fast approximate nearest neighbor search with the navigating spreading-out graph
Fu, C., Xiang, C., Wang, C., & Cai, D. (2019) · Proceedings of the VLDB Endowment · doi:10.14778/3303753.3303754 · Cited by 379
ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms
Aumüller, M., Bernhardsson, E., & Faithfull, A. (2020) · Information Systems · doi:10.1016/j.is.2019.02.006 · Cited by 300
Wang, M., Xu, X., Yue, Q., & Wang, Y. (2021) · Proceedings of the VLDB Endowment · doi:10.14778/3476249.3476255 · Cited by 264
Metadata
- Authors
- Malkov, Y., Ponomarenko, A., Logvinov, A., & Krylov, V.
- Venue
- Information Systems
- Publisher
- Elsevier BV
- Published
- 2014-09
- Volume
- 45
- Pages
- 61-68
- ISSN
- 0306-4379 (ISSN-L)
- OpenAlex
- W2086179657
- Cited by
- 419
- References
- 33
- FWCI
- 8.55
- 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.