The DOI matches its Crossref record; 55 of the 55 references it cites were found in a registry or an index.
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Open accessAbstract
Consider a set of S of n data points in real d -dimensional space, R d , where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess S into a data structure, so that given any query point q ∈ R d , is the closest point of S to q can be reported quickly. Given any positive real ϵ, data point p is a (1 +ϵ)- approximate nearest neighbor of q if its distance from q is within a factor of (1 + ϵ) of the distance to the true nearest neighbor. We show that it is possible to preprocess a set of n points in R d in O(dn log n ) time and O(dn) space, so that given a query point q ∈ R d , and ϵ > 0, a (1 + ϵ)-approximate nearest neighbor of q can be computed in O ( c d , ϵ log n ) time, where c d,ϵ ≤ d ⌈1 + 6d/ϵ⌉ d is a factor depending only on dimension and ϵ. In general, we show that given an integer k ≥ 1, (1 + ϵ)-approximations to the k nearest neighbors of q can be computed in additional O(kd log n ) time.
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
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Nearest neighbor pattern classification
Cover, T., & Hart, P. (1967) · IEEE Transactions on Information Theory · doi:10.1109/tit.1967.1053964 · Cited by 16,936
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
(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
Computational Geometry: Algorithms and Applications
de Berg, M., Cheong, O., van Kreveld, M. J., & Overmars, M. H. (1997) · CERN Document Server (European Organization for Nuclear Research) · Cited by 4,450
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
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
Preparata, F. P., & Shamos, M. I. (1985) · Springer eBooks · doi:10.1007/978-1-4612-1098-6 · Cited by 3,655
Pattern Classification and Scene Analysis.
Clarke, M. R. B., Duda, R. O., & Hart, P. E. (1974) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2344977 · Cited by 3,222
Fibonacci heaps and their uses in improved network optimization algorithms
Fredman, M. L., & Tarjan, R. E. (1987) · Journal of the ACM · doi:10.1145/28869.28874 · Cited by 3,132
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
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
The design and analysis of spatial data structures
Samet, H. (1989) · CERN Document Server (European Organization for Nuclear Research) · Cited by 2,380
Algorithms in Combinatorial Geometry.
Goodman, J. E., & Edelsbrunner, H. (1989) · The American Mathematical Monthly · doi:10.2307/2325168 · Cited by 1,788
O’Regan, G. (2023) · Texts in Computer Science · doi:10.1007/978-3-031-26212-8_4 · Cited by 1,614
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
Roussopoulos, N., Kelley, S., & Vincent, F. (1995) · Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95 · doi:10.1145/223784.223794 · Cited by 1,402
Berchtold, S., Keim, D. A., & Kriegel, H.-P. (2002) · Readings in Multimedia Computing and Networking · doi:10.1016/b978-155860651-7/50124-8 · Cited by 1,118
A data structure for dynamic trees
Sleator, D. D., & Tarjan, R. E. (1983) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(83)90006-5 · Cited by 1,018
Computational Geometry: Algorithms and Applications
de Berg, M., van Kreveld, M., Overmars, M., & Schwarzkopf, O. (1997) · Springer eBooks · doi:10.1007/978-3-662-03427-9 · Cited by 800
A weighted nearest neighbor algorithm for learning with symbolic features
Cost, S., & Salzberg, S. (1993) · Machine Learning · doi:10.1007/bf00993481 · Cited by 764
Similarity indexing with the SS-tree
White, D. A., & Jain, R. (2002) · Proceedings of the Twelfth International Conference on Data Engineering · doi:10.1109/icde.1996.492202 · Cited by 635
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
Self-citationCallahan, P. B., & Kosaraju, S. R. (1995) · Journal of the ACM · doi:10.1145/200836.200853 · Cited by 543
The TV-tree: An index structure for high-dimensional data
Lin, K.-I., Jagadish, H. V., & Faloutsos, C. (1994) · The VLDB Journal · doi:10.1007/bf01231606 · Cited by 494
Optimal algorithms for approximate clustering
Feder, T., & Greene, D. (1988) · doi:10.1145/62212.62255 · Cited by 437
The X Tree: An Index Structure for High Dimensional Data
Berchtold, S., Keim, D. A., & Kriegel, H.-P. (1996) · KOPS (University of Konstanz) · Cited by 414
An improvement of the minimum distortion encoding algorithm for vector quantization
Bei, C.-D., & Gray, R. M. (1985) · IEEE Transactions on Communications · doi:10.1109/tcom.1985.1096214 · Cited by 411
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
A cost model for nearest neighbor search in high-dimensional data space
Berchtold, S., Böhm, C., Keim, D. A., & Kriegel, H.-P. (1997) · Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems · doi:10.1145/263661.263671 · Cited by 373
Refinements to nearest-neighbor searching ink-dimensional trees
Sproull, R. F. (1991) · Algorithmica · doi:10.1007/bf01759061 · Cited by 349
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
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
Approximate nearest neighbor queries in fixed dimensions
Arya, S., & Mount, D. M. (1993) · doi:10.5555/313559.313768 · Cited by 303
Self-citationA theorem on polygon cutting with applications
Chazelle, B. (1982) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1982.58 · Cited by 277
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
A Randomized Algorithm for Closest-Point Queries
Clarkson, K. L. (1988) · SIAM Journal on Computing · doi:10.1137/0217052 · Cited by 248
AnO(n logn) algorithm for the all-nearest-neighbors Problem
Vaidya, P. M. (1989) · Discrete & Computational Geometry · doi:10.1007/bf02187718 · Cited by 232
Ray Shooting and Parametric Search
Agarwal, P. K., & Matoušek, J. (1993) · SIAM Journal on Computing · doi:10.1137/0222051 · Cited by 172
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
Equal-average hyperplane partitioning method for vector quantization of image data
Guan, L., & Kamel, M. S. (1992) · Pattern Recognition Letters · doi:10.1016/0167-8655(92)90098-k · Cited by 94
Fast closest codeword search algorithms for vector quantisation
Lee, C.-H. (1994) · IEE Proceedings - Vision Image and Signal Processing · doi:10.1049/ip-vis:19941140 · Cited by 88
Approximate closest-point queries in high dimensions
Bern, M. W. (1993) · Information Processing Letters · doi:10.1016/0020-0190(93)90222-u · Cited by 83
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 82
Arya, S., & Mount, D. M. (1995) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/220279.220298 · Cited by 54
Self-citationIp, L., JagadishH., V., & FaloutsosChristos (1994) · Very Large Data Bases · doi:10.5555/615204.615210 · Cited by 53
(2021) · Lecture notes in computer science · doi:10.1007/978-3-030-75765-6 · Cited by 53
Accounting for boundary effects in nearest neighbor searching
Arya, S., Mount, D. M., & Narayan, O. (1995) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/220279.220315 · Cited by 43
Self-citationApproximate nearest neighbor queries revisited
Chan, T. M. (1997) · doi:10.1145/262839.263001 · Cited by 33
On the Optimality of Elia's Algorithm for Performing Best-Match Searches.
Rivest, R. L. (1974) · IFIP Congress · Cited by 32
(1990)
Research works printed but not linked: 15
- 10.1109/DCC.1993.253111 · doi:10.1109/dcc.1993.253111
- 10.1145/220279.220296 · doi:10.1145/220279.220296
- 10.1145/129712.129766 · doi:10.1145/129712.129766
- CALLAHAN , P. B. , AND KOSARAJU , S.U. 1995 . Algorithms for dynamic closest pair and n-body potential fields . In Proceedings of the 6th Annual A CM-SIAM Symposium on Discrete Algorithms ( San Francisco, Calif., Jan. 22-24). ACM, New York , pp. 263 - 272 . CALLAHAN, P. B., AND KOSARAJU, S.U. 1995. Algorithms for dynamic closest pair and n-body potential fields. In Proceedings of the 6th Annual A CM-SIAM Symposium on Discrete Algorithms (San Francisco, Calif., Jan. 22-24). ACM, New York, pp. 263-272.
- 10.1109/SFCS.1983.16 · doi:10.1109/sfcs.1983.16
- 10.1145/355826.355832 · doi:10.1145/355826.355832
- 10.1023/A:1022664626993 · doi:10.1023/a:1022664626993 · Paper page
- 10.1109/TIT.1985.1057040 · doi:10.1109/tit.1985.1057040
- FAYYAD , U. M. , PIATETSKY-SHAPIRO , G. , SMYTH , P. , AND UTHURUSAMY , R. 1996. Advances in Knowledge Discovery and Data Mining . AAAI Press/MIT Press , Cambridge, Mass . FAYYAD, U. M., PIATETSKY-SHAPIRO, G., SMYTH, P., AND UTHURUSAMY, R. 1996. Advances in Knowledge Discovery and Data Mining. AAAI Press/MIT Press, Cambridge, Mass.
- 10.1137/0214055 · doi:10.1137/0214055
- FREDERICKSON , G.N. 1993 . A data structure for dynamically maintaining rooted trees . In Proceedings of the 4th Annual A CM-SIAM Symposium on Discrete Algorithms. ACM , New York , pp. 175 - 194 . FREDERICKSON, G.N. 1993. A data structure for dynamically maintaining rooted trees. In Proceedings of the 4th Annual A CM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 175-194.
- GALPERIN , I. , AND RIVEST , R. L. 1993 . Scapegoat trees . In Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms. ACM , New York , pp. 165 - 174 . GALPERIN, I., AND RIVEST, R. L. 1993. Scapegoat trees. In Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 165-174.
- MOUNT , D. M. , NETANYAHU , N. , SILVERMAN , R. , AND WU , A. Y. 1995 . Chromatic nearest neighbor searching: A query sensitive approach . In Proceedings of the 7th Canadian Conference on Computer Geometry. (Quebec City, Que., Canada, Aug. 10-13) . pp. 261 - 266 . MOUNT, D. M., NETANYAHU, N., SILVERMAN, R., AND WU, A. Y. 1995. Chromatic nearest neighbor searching: A query sensitive approach. In Proceedings of the 7th Canadian Conference on Computer Geometry. (Quebec City, Que., Canada, Aug. 10-13). pp. 261-266.
- 10.1007/BF01377181 · doi:10.1007/bf01377181
- 10.5555/645481.655573 · doi:10.5555/645481.655573
Cited by
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
Content-based image retrieval at the end of the early years
Smeulders, A. W. M., Worring, M., Santini, S., Gupta, A., & Jain, R. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.895972 · Cited by 6,056
An efficient k-means clustering algorithm: analysis and implementation
Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., & Wu, A. Y. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2002.1017616 · Cited by 5,660
Self-citationSampling-based algorithms for optimal motion planning
Karaman, S., & Frazzoli, E. (2011) · The International Journal of Robotics Research · doi:10.1177/0278364911406761 · Cited by 5,275
Ridge-based vessel segmentation in color images of the retina
Staal, J., Abramoff, M. D., Niemeijer, M., Viergever, M. A., & van Ginneken, B. (2004) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2004.825627 · Cited by 4,202
Metadata
- Authors
- Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y.
- Venue
- Journal of the ACM
- Published
- 1998-11
- Volume
- 45
- Issue
- 6
- Pages
- 891-923
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2427881153
- Cited by
- 2,300
- References
- 55
- FWCI
- 37.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.