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
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
