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
Items 501–600 of 1,008
k*-Nearest Neighbors: From Global to LocalPreprint
Anava, O., & Levy, K. Y. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1701.07266 · Cited by 69
Deep Neural Network Based Malware Detection Using Two Dimensional Binary Program FeaturesPreprint
Saxe, J., & Berlin, K. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1508.03096 · Cited by 75
Polynomial Representations of Threshold Functions and Algorithmic Applications
Alman, J., Chan, T. M., & Williams, R. (2016) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2016.57 · Cited by 68
Critical analysis of DBSCAN variations
Ali, T. M., Asghar, S., & Sajid, N. A. (2010) · International Conference on Information and Emerging Technologies · doi:10.1109/iciet.2010.5625720 · Cited by 68
Ailon, N., & Chazelle, B. (2010) · Communications of the ACM · doi:10.1145/1646353.1646379 · Cited by 68
Time Series Analysis Using Geometric Template Matching
Frank, J., Mannor, S., Pineau, J., & Precup, D. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.121 · Cited by 68
A hybrid layout algorithm for sub-quadratic multidimensional scaling
Morrison, A., Ross, G., & Chalmers, M. (2003) · IEEE Symposium on Information Visualization · doi:10.1109/infvis.2002.1173161 · Cited by 68
A Group Testing Framework for Similarity Search in High-dimensional Spaces
Shi, M., Furon, T., & Jeǵou, H. (2014) · ACM International Conference on Multimedia (ACM MM) · doi:10.1145/2647868.2654895 · Cited by 67
Manasse, M. S., McSherry, F., & Talwar, K. (2007) · Cited by 67
Training Echo State Networks with Regularization Through Dimensionality Reduction
Løkse, S., Bianchi, F. M., & Jenssen, R. (2017) · Cognitive Computation · doi:10.1007/s12559-017-9450-z · Cited by 67
Query-by-Example Search with Discriminative Neural Acoustic Word Embeddings
Settle, S., Levin, K., Kamper, H., & Livescu, K. (2017) · Interspeech (USB) · doi:10.21437/interspeech.2017-1592 · Cited by 73
Spreading vectors for similarity search
Sablayrolles, A., Douze, M., Schmid, C., & Jégou, H. (2018) · arXiv · doi:10.48550/arxiv.1806.03198 · Cited by 66
Spectral Embedded Hashing for Scalable Image Retrieval
Chen, L., Xu, D., Tsang, I. W.-H., & Li, X. (2013) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2013.2281366 · Cited by 66
Locality-sensitive hashing for the edit distance
Marçais, G., DeBlasio, D., Pandey, P., & Kingsford, C. (2019) · Bioinformatics · doi:10.1093/bioinformatics/btz354 · Cited by 66
ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data
Patel, L., Kraft, P., Guestrin, C., & Zaharia, M. (2024) · Proceedings of the ACM on Management of Data · doi:10.1145/3654923 · Cited by 66
Schubert, E., Weiler, M., & Kriegel, H. (2014) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2623330.2623740 · Cited by 66
Privacy Preserving Nearest Neighbor Search
Shaneck, M., Kim, Y., & Kumar, V. (2006) · IEEE ... International Conference on Data Mining workshops · doi:10.1109/icdmw.2006.133 · Cited by 66
Streaming algorithms for embedding and computing edit distance in the low distance regime
Chakraborty, D., Goldenberg, E., & Koucký, M. (2016) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2897518.2897577 · Cited by 66
Zheng, Y., Guo, Q., Tung, A. K. H., & Wu, S. (2016) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2882903.2882930 · Cited by 68
Compact Random Feature MapsPreprint
Hamid, R., Xiao, Y., Gittens, A., & DeCoste, D. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1312.4626 · Cited by 66
Inertial Sensing Meets Machine Learning: Opportunity or Challenge?
Li, Y., Chen, R., Niu, X., Zhuang, Y., Gao, Z., Hu, X., & El‐Sheimy, N. (2021) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2021.3097385 · Cited by 67
Software Similarity and Classification
Cesare, S., & Xiang, Y. (2012) · SpringerBriefs in computer science · doi:10.1007/978-1-4471-2909-7 · Cited by 66
Dimensionality Reduction with Subgaussian Matrices: A Unified Theory
Dirksen, S. (2015) · Foundations of Computational Mathematics · doi:10.1007/s10208-015-9280-x · Cited by 65
Nasr, M., Houmansadr, A., & Mazumdar, A. (2017) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3133956.3134074 · Cited by 72
Generation of Cancelable Iris Templates via Randomized Bit Sampling
Sadhya, D., & Raman, B. (2019) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2019.2907014 · Cited by 65
Random Forest for Image Annotation
Fu, H., Zhang, Q., & Qiu, G. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33783-3_7 · Cited by 64
Real-time recommendation of diverse related articles
Abbar, S., Amer-Yahia, S., Indyk, P., & Mahabadi, S. (2013) · International World Wide Web Conference (WWW) · doi:10.1145/2488388.2488390 · Cited by 64
Self-citationGraph Cuts for Supervised Binary Coding
Ge, T., He, K., & Sun, J. Z. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-10584-0_17 · Cited by 64
Improving Random Projections Using Marginal Information
Li, P., Hastie, T. J., & Church, K. (2006) · Lecture notes in computer science · doi:10.1007/11776420_46 · Cited by 64
Unsupervised discovery of co-occurrence in sparse high dimensional data
Chum, O., & Matas, J. (2010) · 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.2010.5539997 · Cited by 64
Buffer k-d Trees: Processing Massive Nearest Neighbor Queries on GPUs
Gieseke, F. C., Heinermann, J., Oancea, C. E., & Igel, C. (2014) · Cited by 64
Pyramid Match Hashing: Sub-Linear Time Indexing Over Partial Correspondences
Grauman, K. L., & Darrell, T. (2007) · 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.2007.383225 · Cited by 64
Locality-Sensitive Bloom Filter for Approximate Membership Query
Hua, Y., Xiao, B., Veeravalli, B., & Feng, D. (2011) · IEEE Transactions on Computers · doi:10.1109/tc.2011.108 · Cited by 64
Cormode, G. (2026) · Warwick Research Archive Portal (University of Warwick) · doi:10.82444/warw.33642484 · Cited by 64
Knowing when to put your foot down
Ikemoto, L., Arıkan, O., & Forsyth, D. A. (2006) · ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D) · doi:10.1145/1111411.1111420 · Cited by 64
Top-k Similarity Join in Heterogeneous Information Networks
Xiong, Y., Zhu, Y., & Yu, P. S. (2014) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2014.2373385 · Cited by 63
Efficient large-scale image annotation by probabilistic collaborative multi-label propagation
Chen, X., Mu, Y., Yan, S., & Chua, T. (2010) · ACM International Conference on Multimedia (ACM MM) · doi:10.1145/1873951.1873959 · Cited by 63
Efficient Distributed Density Peaks for Clustering Large Data Sets in MapReduce
Zhang, Y., Chen, S., & Yu, G. (2016) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2016.2609423 · Cited by 63
Distributed PCP Theorems for Hardness of Approximation in P
Abboud, A., Rubinstein, A., & Williams, R. (2017) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2017.12 · Cited by 63
Magen, A. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45726-7_19 · Cited by 63
Lower bounds for predecessor searching in the cell probe model
Sen, P., & Venkatesh, S. (2007) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.06.016 · Cited by 62
Dimension Independent Similarity Computation
Bosagh, Z., & GoelAshish (2012) · doi:10.48550/arxiv.1206.2082 · Cited by 62
Subspace embeddings for the L 1 -norm with applications
Sohler, C., & Woodruff, D. P. (2011) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1993636.1993736 · Cited by 62
Locality Sensitive Outlier Detection: A ranking driven approach
Wang, Y., Parthasarathy, S., & Tatikonda, S. (2011) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2011.5767852 · Cited by 62
New analysis of manifold embeddings and signal recovery from compressive measurements
Eftekhari, A., & Wakin, M. B. (2014) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2014.08.005 · Cited by 62
Valiant, G. J. (2015) · Journal of the ACM · doi:10.1145/2728167 · Cited by 62
Lu, K., Wang, H., Wang, W., & Kudo, M. (2020) · Proceedings of the VLDB Endowment · doi:10.14778/3397230.3397240 · Cited by 62
Chen, B., Medini, T., Farwell, J., Gobriel, S., Tai, C., & Shrivastava, A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1903.03129 · Cited by 62
Large-Scale Unsupervised Hashing with Shared Structure Learning
Liu, X., Mu, Y., Zhang, D., Lang, B., & Li, X. (2014) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2014.2360856 · Cited by 61
MI-File: using inverted files for scalable approximate similarity search
Amato, G. M., Gennaro, C., & Savino, P. (2012) · Multimedia Tools and Applications · doi:10.1007/s11042-012-1271-1 · Cited by 61
Semantics-aware detection of targeted attacks: a survey
Luh, R., Marschalek, S., Kaiser, M., Janicke, H., & Schrittwieser, S. (2016) · Journal of Computer Virology and Hacking Techniques · doi:10.1007/s11416-016-0273-3 · Cited by 64
Training neural networks on high-dimensional data using random projection
Wójcik, P. I., & Kurdziel, M. (2018) · Pattern Analysis and Applications · doi:10.1007/s10044-018-0697-0 · Cited by 64
A survey on graph-based methods for similarity searches in metric spaces
Shimomura, L. C., Oyamada, R. S., Vieira, M. R., & Kaster, D. S. (2020) · Information Systems · doi:10.1016/j.is.2020.101507 · Cited by 63
Antipole tree indexing to support range search and k-nearest neighbor search in metric spaces
Cantone, D. A., Ferro, A., Pulvirenti, A., Recupero, D. R., & Shasha, D. E. (2005) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2005.53 · Cited by 61
Barnes-Hut-SNEPreprint
van der Maaten, L. (2013) · arXiv (Cornell University) · Cited by 61
Graph-based bag-of-words for classification
Silva, F. B., Werneck, R. D. O., Goldenstein, S. K., Tabbone, S., & Torres, R. D. S. (2017) · Pattern Recognition · doi:10.1016/j.patcog.2017.09.018 · Cited by 60
Memari, P., Mohammadi, S. S., Jolai, F., & Tavakkoli-Moghaddam, R. R. (2021) · The Journal of Supercomputing · doi:10.1007/s11227-021-03868-4 · Cited by 60
Audio Fingerprinting: Nearest Neighbor Search in High Dimensional Binary Spaces
Miller, M. L., Rodriguez, M. A., & Cox, I. J. (2005) · The Journal of VLSI Signal Processing Systems for Signal Image and Video Technology · doi:10.1007/s11265-005-4152-2 · Cited by 60
Xia, Y., He, K., Wen, F., & Sun, J. Z. (2013) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2013.424 · Cited by 60
Query expansion for hash-based image object retrieval
Kuo, Y.-H., Chen, K., Chiang, C.-H., & Hsu, W. H. (2009) · ACM International Conference on Multimedia (ACM MM) · doi:10.1145/1631272.1631284 · Cited by 60
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching
Chakrabarti, A., & Regev, O. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.12 · Cited by 60
Probabilistic data structures for big data analytics: A comprehensive review
Singh, A., Garg, S., Kaur, R., Batra, S., Kumar, N., & Zomaya, A. Y. (2019) · Knowledge-Based Systems · doi:10.1016/j.knosys.2019.104987 · Cited by 60
Active learning via query synthesis and nearest neighbour search
Wang, L., Hu, X., Yuan, B., & Lu, J. (2015) · Neurocomputing · doi:10.1016/j.neucom.2014.06.042 · Cited by 59
TextGNN: Improving Text Encoder via Graph Neural Network in Sponsored Search
Zhu, J., Cui, Y., Liu, Y., Sun, H., Li, X., Pelger, M., Yang, T., Zhang, L., Zhang, R., & Zhao, H. (2021) · International World Wide Web Conference (WWW) · doi:10.1145/3442381.3449842 · Cited by 64
Min-Max Hash for Jaccard Similarity
Ji, J., Li, J., Yan, S., Tian, Q., & Zhang, B. (2013) · Proceedings · doi:10.1109/icdm.2013.119 · Cited by 62
Deep Variational and Structural Hashing
Liong, V. E., Lu, J., Duan, L., & Tan, Y. (2018) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2018.2882816 · Cited by 59
Dimensionality reduction techniques for proximity problems
Indyk, P. (2000) · doi:10.5555/338219.338582 · Cited by 59
Self-citationDBSCAN++: Towards fast and scalable density clusteringPreprint
Jang, J., & Jiang, H. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.13105 · Cited by 59
ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge GraphsPreprint
Zhang, Z., Wang, J., Chen, J., Ji, S., & Wu, F. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.13715 · Cited by 61
Robust and Sparse Principal Component Analysis With Adaptive Loss Minimization for Feature Selection
Bian, J., Zhao, D., Nie, F., Wang, R., & Li, X. (2022) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3194896 · Cited by 59
Compressed labeling on distilled labelsets for multi-label learning
Zhou, T., Tao, D., & Wu, X. (2012) · Machine Learning · doi:10.1007/s10994-011-5276-1 · Cited by 58
A fast nearest neighbor search algorithm by nonlinear embedding
Hwang, Y., Han, B., & Hee-kap Ahn, A. (2012) · 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.2012.6248036 · Cited by 58
Using Word Embeddings to Enhance Keyword Identification for Scientific Publications
Wang, R., Liu, W., & McDonald, C. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-19548-3_21 · Cited by 58
FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity SearchPreprint
Singh, A., Subramanya, S. J., Krishnaswamy, R., & Simhadri, H. V. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2105.09613 · Cited by 138
PatchMatchGraph: Building a Graph of Dense Patch Correspondences for Label Transfer
Gould, S. J., & Zhang, Y. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33715-4_32 · Cited by 57
A Fast k-Nearest Neighbor Classifier Using Unsupervised Clustering
Vajda, S., & Santosh, K. (2017) · Communications in computer and information science · doi:10.1007/978-981-10-4859-3_17 · Cited by 57
Yang, Q., Ji, H., Xu, Z., Li, Y., Wang, P., Sun, J., Fan, X., Zhang, H., Lü, H., & Zhang, Z. (2023) · Nature Communications · doi:10.1038/s41467-023-39279-7 · Cited by 57
Vector Database Management Techniques and Systems
Pan, J. J., Wang, J., & Li, G. (2024) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3626246.3654691 · Cited by 57
Johnson‐Lindenstrauss lemma for circulant matrices**
Hinrichs, A., & Vybíral, J. (2011) · Random Structures and Algorithms · doi:10.1002/rsa.20360 · Cited by 57
Link-Based Similarity Search to Fight Web Spam
Benczúr, A. A., Csalogány, K., & Sarlós, T. (2006) · Cited by 57
Brokos, G.-I., Malakasiotis, P., & Androutsopoulos, I. (2016) · Workshop on Biomedical Language Processing (BioNLP) · doi:10.18653/v1/w16-2915 · Cited by 57
Traganitis, P. A., & Giannakis, G. B. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2781649 · Cited by 57
Deformable spanners and applications
Gao, J., Guibas, L. J., & Nguyen, T. A. (2004) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/997817.997848 · Cited by 57
Kernel-Based Supervised Discrete Hashing for Image Retrieval
Shi, X., Xing, F., Cai, J., Zhang, Z., Xie, Y., & Yang, L. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-46478-7_26 · Cited by 56
Accurate and Lightweight Image Super-Resolution With Model-Guided Deep Unfolding Network
Ning, Q., Dong, W., Shi, G., Li, L., & Li, X. (2020) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2020.3037516 · Cited by 56
Fingerprint indexing with pose constraint
Su, Y., Feng, J., & Zhou, J. (2016) · Pattern Recognition · doi:10.1016/j.patcog.2016.01.006 · Cited by 56
Learning Sight from Sound: Ambient Sound Provides Supervision for Visual Learning
Owens, A., Wu, J., McDermott, J. H., Freeman, W. T., & Torralba, A. B. (2018) · International Journal of Computer Vision · doi:10.1007/s11263-018-1083-5 · Cited by 61
Generalised kernel weighted fuzzy C-means clustering algorithm with local information
Memon, K. H., & Lee, D.-H. (2018) · Fuzzy Sets and Systems · doi:10.1016/j.fss.2018.01.019 · Cited by 56
The Johnson-Lindenstrauss Lemma Meets Compressed Sensing
Baraniuk, R. G., Davenport, M. A., DeVore, R., & Wakin, M. B. (2006) · Cited by 56
An Improved Algorithm Finding Nearest Neighbor Using Kd-trees
Panigrahy, R. (2008) · Springer eBooks · doi:10.1007/978-3-540-78773-0_34 · Cited by 56
Distance based indexing for string proximity search
Şahinalp, S. C., Tasan, M., Macker, J., & Ozsoyoglu, Z. M. (2004) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2003.1260787 · Cited by 56
Random Projections for Support Vector MachinesPreprint
Paul, S., Boutsidis, C., Magdon‐Ismail, M., & Petros Drineas, B. (2012) · arXiv (Cornell University) · Cited by 56
Multi-View Complementary Hash Tables for Nearest Neighbor Search
Liu, X., Huang, L., Deng, C. D., Lu, J., & Lang, B. (2015) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2015.132 · Cited by 55
Partition Min-Hash for Partial Duplicate Image Discovery
Lee, D. C., Ke, Q., & Isard, M. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15549-9_47 · Cited by 55
Ou, M., Cui, P., Wang, F., Wang, J., Zhu, W., & Yang, S. (2013) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2487575.2487668 · Cited by 55
Lower Bounds on Signatures From Symmetric Primitives
Barak, B., & Mahmoody, M. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.4389536 · Cited by 55
AIDA-light: High-throughput Named-entity Disambiguation
Nguyen, D. B., Hoffart, J., Theobald, M., & Weikum, G. (2014) · Max Planck Digital Library · Cited by 55
Similarity search and locality sensitive hashing using ternary content addressable memories
Shinde, R., Goel, A., Gupta, P. K., & Dutta, D. (2010) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1807167.1807209 · Cited by 55
Entropy-Scaling Search of Massive Biological Data
Yu, Y. W., Daniels, N. M., Danko, D., & Berger, B. (2015) · Cell Systems · doi:10.1016/j.cels.2015.08.004 · Cited by 55
Unsupervised, Efficient and Semantic Expertise Retrieval
Gysel, C. V., de Rijke, M., & Worring, M. (2016) · International World Wide Web Conference (WWW) · doi:10.1145/2872427.2882974 · Cited by 62
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
