The DOI matches its Crossref record; 74 of the 76 references it cites were found in a registry or an index.
Approximate nearest neighbors: towards removing the curse of dimensionality
Abstract
Article Free Access Share on Approximate nearest neighbors: towards removing the curse of dimensionality Authors: Piotr Indyk Department of Computer Science, Stanford University, Stanford, CA Department of Computer Science, Stanford University, Stanford, CAView Profile , Rajeev Motwani Department of Computer Science, Stanford University, Stanford, CA Department of Computer Science, Stanford University, Stanford, CAView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 604–613https://doi.org/10.1145/276698.276876Online:23 May 1998Publication History 2,363citation11,545DownloadsMetricsTotal Citations2,363Total Downloads11,545Last 12 Months769Last 6 weeks97 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“However, SSTH suffers from serious efficiency issue due to the involvement of de-binarization and de-LSTM.”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
In the citing paper
“Given six query videos of different topics, the proposed algorithm makes fewer mistakes in retrieving the similar videos for each query compared with SSTH.”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
In the citing paper
“SSTH [29] / / 8.21h / / 8.23h / / 8.48h / / 8.55h”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
In the citing paper
“For example, the precision@100 at 64 bits reaches 26.1% under the proposed framework and the difference over SSTH (20.4%) is 5.7%.”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
In the citing paper
“For examples, the mAP@5 values at the code length of 128 are 59.3% and 57.1% for UDVH-TSN and UDVH-LSTM on FCVID, which are at least 7% higher than that in SSTH (50.1%).”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
In the citing paper
“Moreover, the UDVH-based methods substantially yield better retrieval performance over SSTH, which is consistent with the results reported in Fig. 5 and further demonstrates the superiority of our self-taught training strategy involving clustering and balanced rotation.”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
In the citing paper
“Considering the deep architectures usually converge within t = 5 loops for the UDVH-based methods, the total training cost is less than 4.5 hours, which is much shorter than training SSTH (over 8 hours), thus indicating the high efficiency of the proposed hashing framework.”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
In the citing paper
“The most time-consuming parts of SSTH include the backpropagation of Binary LSTM units when updating their binary outputs and the complex network structures [29], which are not adopted in our algorithm.”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
In the citing paper
“Specifically, as shown in Fig. 9(a), the mAP@5 values at 128 bits on FCVID are 50.1% and 57.1% for SSTH and UDVH-LSTM, which are over 15% higher than the values achieved when using CNN features.”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
Citations
Cites
An introduction to probability theory and its applications
(1958) · Journal of the Franklin Institute · doi:10.1016/0016-0032(58)90688-4 · Cited by 29,621
Rayward-Smith, V. J., Cormen, T. H., Leiserson, C. E., & Rivest, R. L. (1991) · Journal of the Operational Research Society · doi:10.2307/2583667 · Cited by 16,958
Nearest neighbor pattern classification
Cover, T., & Hart, P. (1967) · IEEE Transactions on Information Theory · doi:10.1109/tit.1967.1053964 · Cited by 16,936
(1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 12,895
Introduction to Modern Information Retrieval
Salton, G., & McGill, M. J. (1983) · Virtual Defense Library (Ministerio de Defensa) · Cited by 9,743
Analysis of a complex of statistical variables into principal components.
Hotelling, H. (1933) · Journal of Educational Psychology · doi:10.1037/h0071325 · Cited by 9,691
Multidimensional binary search trees used for associative searching
Bentley, J. L. (1975) · Communications of the ACM · doi:10.1145/361002.361007 · Cited by 7,498
Vector Quantization and Signal Compression
Gersho, A., & Gray, R. M. (1992) · Springer eBooks · doi:10.1007/978-1-4615-3626-0 · Cited by 7,055
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,098
Self-citationPattern classification and scene analysis
Chien, Y. (1974) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1974.1100577 · Cited by 3,421
(1999) · Cited by 3,186
Self-citationQuery 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., Petković, D., et al. (1995) · Computer · doi:10.1109/2.410146 · Cited by 3,097
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,802
Information Retrieval: Data Structures and Algorithms
Frakes, W. B., & Baeza-Yates, R. A. (1992) · Cited by 2,423
The design and analysis of spatial data structures
Samet, H. (1989) · CERN Document Server (European Organization for Nuclear Research) · Cited by 2,380
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,290
On the resemblance and containment of documents
Broder, A. (2002) · Compression and Complexity of Sequences (SEQUENCES) · doi:10.1109/sequen.1997.666900 · Cited by 1,818
Algorithms in Combinatorial Geometry.
Goodman, J. E., & Edelsbrunner, H. (1989) · American Mathematical Monthly · doi:10.2307/2325168 · Cited by 1,800
Query by Image and Video Content: The QBIC System
Flickner, M., Sawhney, H., Niblack, W., Ashley, J. J., Huang, Q., Dom, B., Gorkani, M., Hafner, J., Lee, D., Petković, D., et al. (2002) · Elsevier eBooks · doi:10.1016/b978-155860651-7/50108-x · Cited by 1,559
Algorithms in Combinatorial Geometry
Edelsbrunner, H. (1987) · Springer eBooks · doi:10.1007/978-3-642-61568-9 · Cited by 1,536
Syntactic clustering of the Web
Broder, A., Glassman, S. C., Manasse, M. S., & Zweig, G. (1997) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(97)00031-7 · Cited by 1,348
Efficient and effective Querying by Image Content
Faloutsos, C., Barber, R., Flickner, M., Hafner, J., Niblack, W., Petković, D., & Equitz, W. (1994) · Journal of Intelligent Information Systems · doi:10.1007/bf00962238 · Cited by 1,250
Shamos, M. I., & Hoey, D. (1975) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1975.8 · Cited by 1,070
Pattern Classification and Scene Analysis.
Grenander, U., Duda, R. O., & Hart, P. E. (1974) · Journal of the American Statistical Association · doi:10.2307/2286028 · Cited by 1,035
(1993) · doi:10.5555/313559.313789 · Cited by 998
The Volume of Convex Bodies and Banach Space Geometry
Pisier, G. (1989) · Cambridge University Press eBooks · doi:10.1017/cbo9780511662454 · Cited by 997
Mapping authors in intellectual space: A technical overview
McCain, K. W. (1990) · Journal of the American Society for Information Science · doi:10.1002/(sici)1097-4571(199009)41:6 · Cited by 987
The geometry of graphs and some of its algorithmic applications
Linial, N., London, E., & Rabinovich, Y. G. (1995) · COMBINATORICA · doi:10.1007/bf01200757 · Cited by 972
Photobook: tools for content-based manipulation of image databases
Pentland, A. P., Picard, R. W., & Scarloff, S. (1994) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.171786 · Cited by 882
Discriminant adaptive nearest neighbor classification
Hastie, T., & Tibshirani, R. J. (1996) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.506411 · Cited by 833
A Weighted Nearest Neighbor Algorithm for Learning with Symbolic Features
Cost, S., & Salzberg, S. L. (1993) · Machine Learning · doi:10.1023/a:1022664626993 · Cited by 771
Storing a Sparse Table with 0 (1) Worst Case Access Time
Fredman, M. L., Komlós, J., & Szemerédi, E. (1984) · Journal of the ACM · doi:10.1145/828.1884 · Cited by 759
Über lineare Methoden in der Wahrscheinlichkeitsrechnung
Karhunen, K. (1947) · Suomalainen Tiedeakatemia eBooks · Cited by 706
Applications of a Planar Separator Theorem
Lipton, R. J., & Tarjan, R. E. (1980) · SIAM Journal on Computing · doi:10.1137/0209046 · Cited by 645
Applying Parallel Computation Algorithms in the Design of Serial Algorithms
Megiddo, N. (1983) · Journal of the ACM · doi:10.1145/2157.322410 · Cited by 632
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 590
Callahan, P. B., & Kosaraju, S. R. (1995) · Journal of the ACM · doi:10.1145/200836.200853 · Cited by 550
Some approaches to best-match file searching
Burkhard, W. A., & Keller, R. (1973) · Communications of the ACM · doi:10.1145/362003.362025 · Cited by 415
The design and analysis of spatial data structures
Egenhofer, M. J. (1991) · ISPRS Journal of Photogrammetry and Remote Sensing · doi:10.1016/0924-2716(91)90007-i · Cited by 368
Two algorithms for nearest-neighbor search in high dimensions
Kleinberg, J. M. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258653 · Cited by 347
Distance-based indexing for high-dimensional metric spaces
Bozkaya, T., & Özsoyoğlu, M. (1997) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/253260.253345 · Cited by 334
New Retrieval Approaches Using SMART: TREC 4.
Buckley, C., Singhal, A., Mitra, M., & Salton, G. (1995) · Cited by 319
Approximate nearest neighbor queries in fixed dimensions
Arya, S., & Mount, D. M. (1993) · doi:10.5555/313559.313768 · Cited by 314
The Johnson-Lindenstrauss lemma and the sphericity of some graphs
Frankl, P., & Maehara, H. (1988) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(88)90043-3 · Cited by 310
Efficient search for approximate nearest neighbor in high dimensional spaces
Eyal Kushilevitz, Z., Ostrovsky, R., & Rabani, Y. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276877 · Cited by 261
Multidimensional Searching Problems
Dobkin, D., & Lipton, R. J. (1976) · SIAM Journal on Computing · doi:10.1137/0205015 · Cited by 250
A Randomized Algorithm for Closest-Point Queries
Clarkson, K. L. (1988) · SIAM Journal on Computing · doi:10.1137/0217052 · Cited by 249
Reporting points in halfspaces
Matous̆ek, J. (1992) · Computational Geometry · doi:10.1016/0925-7721(92)90006-e · Cited by 236
Ray Shooting and Parametric Search
Agarwal, P. K., & Matoušek, J. (1993) · SIAM Journal on Computing · doi:10.1137/0222051 · Cited by 173
Nearest Neighbor Queries in Metric Spaces
Clarkson, K. L. (1999) · Discrete & Computational Geometry · doi:10.1007/pl00009449 · Cited by 169
Point Location in Arrangements of Hyperplanes
Meiser, S. (1993) · Information and Computation · doi:10.1006/inco.1993.1057 · Cited by 156
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
FLASH: a fast look-up algorithm for string homology.
Califano, A., & Rigoutsos, I. (1993) · PubMed · Cited by 106
Multi-index hashing for information retrieval
Greene, D., Parnas, M., & Yao, F. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365720 · Cited by 97
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
Approximate Nearest Neighbor Queries Revisited
Chan, T. M. (1998) · Discrete & Computational Geometry · doi:10.1007/pl00009390 · Cited by 80
Geometric matching under noise: combinatorial bounds and algorithms
Indyk, P., Motwani, R., & Venkatasubramanian, S. (1999) · Cited by 67
Self-citationNearest neighbor queries in metric spaces
Clarkson, K. L. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258655 · Cited by 59
Embedding l ${}_{p}^{m}$ into l ${}_{1}^{n}$
Johnson, W. B., & Schechtman, G. (1982) · Acta Mathematica · doi:10.1007/bf02392350 · Cited by 57
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
Fast hierarchical clustering and other applications of dynamic closest pairsPreprint
Eppstein, D. (1998) · doi:10.5555/314613.315030 · Cited by 39
Subquadratic approximation algorithms for clustering problems in high dimensional spaces
Borodin, A., Ostrovsky, R., & Rabani, Y. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301367 · Cited by 38
Multidimensional Access Methods: Trees Have Grown Everywhere
Sellis, T., Roussopoulos, N., & Faloutsos, C. (1997) · Very Large Data Bases · Cited by 36
Approximate nearest neighbor queries revisited
Chan, T. M. (1997) · doi:10.1145/262839.263001 · Cited by 33
Finding the neighborhood of a query in a dictionary
Dolev, D., Harari, Y., & Parnas, M. (2002) · doi:10.1109/istcs.1993.253486 · Cited by 20
The bit vector intersection problem
Karp, R. M., Waarts, O., & Zweig, G. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1995.492663 · Cited by 19
Neighborhood preserving hashing and approximate queries
Dolev, D., Harari, Y. N., Linial, N., Nisan, N., & Parnas, M. (1994) · Symposium on Discrete Algorithms · doi:10.5555/314464.314501 · Cited by 18
Paturi, R., Rajasekaran, S., & Reif, J. H. (1995) · Information and Computation · doi:10.1006/inco.1995.1038 · Cited by 17
Neighborhood Preserving Hashing and Approximate Queries
Dolev, D., Harari, Y., Linial, N., Nisan, N., & Parnas, M. (2001) · SIAM Journal on Discrete Mathematics · doi:10.1137/s089548019731809x · Cited by 13
Static Dictionaries on RAMs: Query Time is Necessary and Sufficient
Andersson, A. (1996) · Cited by 13
A Case Study of Latent Semantic Indexing
Berry, M. W., & Shippy, A. T. (1995) · Cited by 9
Effective nearest neighbors searching on the hyper-cube, with applications to molecular clustering
Cazals, F. (1998) · doi:10.1145/276884.276910 · Cited by 4
Flagged first, then by citations
2 of the 76 references couldn’t be matched to a known paper.
Cited by
Sorted by citations
Distance Metric Learning for Large Margin Nearest Neighbor Classification
Weinberger, K. Q., & Saul, L. K. (2009) · Journal of Machine Learning Research · doi:10.5555/1577069.1577078 · Cited by 4,652
Halko, N., Martinsson, P., & Tropp, J. A. (2011) · SIAM Review · doi:10.1137/090771806 · Cited by 4,038
Scalable Recognition with a Vocabulary Tree
Nistér, D., & Stewénius, H. (2006) · 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.2006.264 · Cited by 3,641
RRT-connect: An efficient approach to single-query path planning
Kuffner, J. J., & LaValle, S. M. (2000) · Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) · doi:10.1109/robot.2000.844730 · Cited by 3,555
Mash: fast genome and metagenome distance estimation using MinHash
Ondov, B. D., Treangen, T. J., Melsted, P., Mallonee, A. B., Bergman, N. H., Koren, S., & Phillippy, A. M. (2016) · Genome biology · doi:10.1186/s13059-016-0997-x · Cited by 3,373
Metadata
- Authors
- Indyk, P., & Motwani, R.
- Affiliations
- Stanford University (US)
- ORCID
- Indyk, Piotr
- Venue
- Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98
- Publisher
- ACM Press
- Published
- 1998
- Pages
- 604-613
- OpenAlex
- W2147717514
- Cited by
- 4,188
- References
- 76
- Citations by year
- 2026: 152 · 2025: 162 · 2024: 164 · 2023: 133 · 2022: 160 · 2021: 223 · 2020: 245 · 2019: 250 · 2018: 249 · 2017: 251 · 2016: 277 · 2015: 280 · 2014: 260 · 2013: 224 · 2012: 208
- FWCI
- 23.46
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM Symposium on Theory of Computing (STOC) (publishedVersion)
- Funders
- National Science Foundation
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Computational Geometry and Mesh Generation
- Physical Sciences › Computer Science › Information Systems › Data Management and Algorithms
- Keywords
- approximate nearest neighbor search, curse of dimensionality, nearest neighbor search, metric spaces, metric embeddings, randomized algorithms
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
