Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
Abstract
We present an algorithm for the c-approximate nearest neighbor problem in a d-dimensional Euclidean space, achieving query time of O(dn1c2/+o(1)) and space O(dn + n1+1c2/+o(1)). This almost matches the lower bound for hashing-based algorithm recently obtained in (R. Motwani et al., 2006). We also obtain a space-efficient version of the algorithm, which uses dn+n logO(1)n space, with a query time of dnO(1/c2). Finally, we discuss practical variants of the algorithms that utilize fast bounded-distance decoders for the Leech lattice
Integrity signals
Registry
Cites
Statistics
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?
Approximate KNN can be obtained efficiently via locality sensitive hashing.
“Approximate KNN can be obtained efficiently via locality sensitive hashing [2].”
From Graph Convolutional Neural Networks for Web-Scale Recommender Systems (2018) · cites this paper as [2]
Cites
Multidimensional binary search trees used for associative searching
Bentley, J. L. (1975) · Communications of the ACM · doi:10.1145/361002.361007 · Cited by 7,659 · see citing works
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 · see citing works
Self-citationGoemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · see citing works
Sphere Packings, Lattices and Groups.
Coxeter, H. S. M., Conway, J. H., & Sloane, N. J. A. (1989) · American Mathematical Monthly · doi:10.2307/2323992 · Cited by 3,373 · see citing works
(1999) · Cited by 3,186 · see citing works
Self-citationLocality-sensitive hashing scheme based on p-stable distributions
Datar, M., Immorlica, N., Indyk, P., & Mirrokni, V. (2004) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/997817.997857 · Cited by 2,971 · see citing works
Self-citationAn 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 · see citing works
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,734 · see citing works
Foundations of Multidimensional and Metric Data Structures
Samet, H., & Gray, J. (2006) · Cited by 1,373 · see citing works
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 · see citing works
The Volume of Convex Bodies and Banach Space Geometry
Pisier, G. (1989) · Cambridge University Press eBooks · doi:10.1017/cbo9780511662454 · Cited by 997 · see citing works
Sphere Packings, Lattices and Groups
Conway, J. H., & Sloane, N. J. A. (1993) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-1-4757-2249-9 · Cited by 880 · see citing works
Min-Wise Independent Permutations
Broder, A., Charikar, M., FRIEZE, A. M., & Mitzenmacher, M. (2000) · Journal of Computer and System Sciences · doi:10.1006/jcss.1999.1690 · Cited by 812 · see citing works
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 · see citing works
Nearest-Neighbor Methods in Learning and Vision
(2006) · The MIT Press eBooks · doi:10.7551/mitpress/4908.001.0001 · Cited by 442 · see citing works
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
Ailon, N., & Chazelle, B. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132597 · Cited by 373 · see citing works
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 · see citing works
Navigating nets: simple algorithms for proximity search
Krauthgamer, R., & Lee, J. R. (2015) · Cited by 308 · see citing works
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 · see citing works
Efficient large-scale sequence comparison by locality-sensitive hashing
Buhler, J. D. (2001) · Bioinformatics · doi:10.1093/bioinformatics/17.5.419 · Cited by 253 · see citing works
Nearest Neighbors in High-Dimensional Spaces
Indyk, P. (2004) · Discrete mathematics and its applications · doi:10.1201/9781420035315.ch39 · Cited by 210 · see citing works
Self-citationRavichandran, D., Pantel, P., & Hovy, E. H. (2005) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.3115/1219840.1219917 · Cited by 206 · see citing works
The geometry of graphs and some of its algorithmic applications
Linial, N., London, E., & Rabinovich, Y. G. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365733 · Cited by 191 · see citing works
Leech, J. (1967) · Canadian Journal of Mathematics · doi:10.4153/cjm-1967-017-0 · Cited by 186 · see citing works
Approximating a finite metric by a small number of tree metrics
Charikar, M., Chekuri, C., Goel, A., Guha, S., & Plotkin, S. A. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1998.743488 · Cited by 175 · see citing works
Soft decoding techniques for codes and lattices, including the Golay code and the Leech lattice
Conway, J., & Sloane, N. J. A. (1986) · IEEE Transactions on Information Theory · doi:10.1109/tit.1986.1057135 · Cited by 165 · see citing works
Finding motifs using random projections
Buhler, J. D., & Tompa, M. (2001) · doi:10.1145/369133.369172 · Cited by 165 · see citing works
Scalable Techniques for Clustering the Web.
Haveliwala, T. H., Gionis, A., & Indyk, P. (2000) · Cited by 148 · see citing works
Self-citationA replacement for Voronoi diagrams of near linear size
Har-Peled, S. (2001) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959884 · Cited by 147 · see citing works
On the optimality of the random hyperplane rounding technique for MAX CUT
Feige, U., & Schechtman, G. (2002) · Random Structures and Algorithms · doi:10.1002/rsa.10036 · Cited by 127 · see citing works
Entropy based nearest neighbor search in high dimensions
Panigrahy, R. (2006) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1145/1109557.1109688 · Cited by 117 · see citing works
High-dimensional computational geometry
Motwani, R., & Indyk, P. (2000) · Cited by 114 · see citing works
Self-citationFLASH: a fast look-up algorithm for string homology
Califano, A., & Rigoutsos, I. (2002) · 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.1993.341106 · Cited by 99 · see citing works
Approximate graph coloring by semidefinite programming
Karger, D. R., Motwani, R., & Sudan, M. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365710 · Cited by 99 · see citing works
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 · see citing works
On the Optimality of the Dimensionality Reduction Method
Andoni, A., Indyk, P., & Pǎtraşcu, M. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.56 · Cited by 95 · see citing works
Self-citationGeneralized minimum-distance decoding of Euclidean-space codes and lattices
Forney, G. D., & Vardy, A. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556693 · Cited by 74 · see citing works
Maximum likelihood decoding of the Leech lattice
Vardy, A., & Be'ery, Y. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.243466 · Cited by 65 · see citing works
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 · see citing works
Lower bounds on locality sensitive hashing
Motwani, R., Naor, A., & Panigrahi, R. (2006) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/1137856.1137881 · Cited by 55 · see citing works
The Leech lattice and the Golay code: bounded-distance decoding and multilevel constructions
Amrani, O., Be'ery, Y., Vardy, A., Sun, F., & van Tilborg, H. C. A. (1994) · IEEE Transactions on Information Theory · doi:10.1109/18.335970 · Cited by 51 · see citing works
Better algorithms for high-dimensional proximity problems via asymmetric embeddings
Indyk, P. (2003) · Cited by 47 · see citing works
Self-citationEfficient algorithms for substring near neighbor problem
Andoni, A., & Indyk, P. (2006) · Cited by 26 · see citing works
Self-citationThe 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 · see citing works
Paturi, R., Rajasekaran, S., & Reif, J. H. (1995) · Information and Computation · doi:10.1006/inco.1995.1038 · Cited by 17 · see citing works
Amrani, O., & Be'ery, Y. (1996) · IEEE Transactions on Communications · doi:10.1109/26.494294 · Cited by 14 · see citing works
Flagged first, then by citations
1 of the 47 references couldn’t be matched to a known paper.
Cited by
Sorted by citations
Graph Convolutional Neural Networks for Web-Scale Recommender Systems
Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W. L., & Leskovec, J. (2018) · Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining · doi:10.1145/3219819.3219890 · Cited by 3,733 · see citing works
FAST APPROXIMATE NEAREST NEIGHBORS WITH AUTOMATIC ALGORITHM CONFIGURATION
(2009) · Proceedings of the Fourth International Conference on Computer Vision Theory and Applications · doi:10.5220/0001787803310340 · Cited by 2,640 · see citing works
Weiss, Y., Torralba, A. B., & Fergus, R. (2008) · neural information processing systems · Cited by 2,389 · see citing works
From Word Embeddings To Document Distances
Kusner, M. J., Sun, Y., Kolkin, N., & Weinberger, K. Q. (2015) · PolyPublie (École Polytechnique de Montréal) · Cited by 1,695 · see citing works
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Andoni, A., & Indyk, P. (2008) · Communications of the ACM · doi:10.1145/1327452.1327494 · Cited by 1,437 · see citing works
Self-citationSalakhutdinov, R., & Hinton, G. (2009) · International Journal of Approximate Reasoning · doi:10.1016/j.ijar.2008.11.006 · Cited by 1,246 · see citing works
Wang, J., Zhang, T., Song, J., Sebe, N., & Shen, H. T. (2017) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2699960 · Cited by 1,034 · see citing works
A survey on unsupervised outlier detection in high‐dimensional numerical data
Zimek, A., Schubert, E., & Kriegel, H. (2012) · Statistical Analysis and Data Mining The ASA Data Science Journal · doi:10.1002/sam.11161 · Cited by 864 · see citing works
Small codes and large image databases for recognition
Torralba, A., Fergus, R., & Weiss, Y. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587633 · Cited by 727 · see citing works
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 666 · see citing works
Self-citationContent-Based Music Information Retrieval: Current Directions and Future Challenges
Casey, M. A., Veltkamp, R. C., Goto, M., Leman, M., Rhodes, C., & Slaney, M. (2008) · Proceedings of the IEEE · doi:10.1109/jproc.2008.916370 · Cited by 656 · see citing works
Feature Learning based Deep Supervised Hashing with Pairwise LabelsPreprint
Li, W.-J., Wang, S., & Kang, W.-C. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.03855 · Cited by 643 · see citing works
Multi-probe LSH: efficient indexing for high-dimensional similarity search
Lv, Q., Josephson, W. K., Wang, Z., Charikar, M., & Li, K. (2007) · Very Large Data Bases · Cited by 634 · see citing works
Inter-media hashing for large-scale retrieval from heterogeneous data sources
Song, J., Yang, Y., Yang, Y., Huang, Z. H., & Shen, H. T. (2013) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2463676.2465274 · Cited by 631 · see citing works
Halder, R. K., Uddin, M. N., Uddin, M. A., Aryal, S., & Khraisat, A. (2024) · Journal Of Big Data · doi:10.1186/s40537-024-00973-y · Cited by 624 · see citing works
Deep hashing for compact binary codes learning
Liong, V. E., Lu, J., Wang, G., Moulin, P., & Zhou, J. (2015) · 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2015.7298862 · Cited by 545 · see citing works
Li, W., Zhang, Y., Sun, Y., Wang, W., Li, M., Zhang, W., & Lin, X. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2909204 · Cited by 501 · see citing works
Learning Hash Functions for Cross-View Similarity Search
Kumar, S., & Udupa, R. (2012) · Cited by 490 · see citing works
What Does Classifying More Than 10,000 Image Categories Tell Us?
Deng, J., Berg, A. C., Li, K., & Fei-Fei, L. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15555-0_6 · Cited by 487 · see citing works
#Exploration: A Study of Count-Based Exploration for Deep Reinforcement LearningPreprint
Tang, H., Houthooft, R., Foote, D., Stooke, A., Chen, X., Duan, Y., Schulman, J., Turck, F. D., & Abbeel, P. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.04717 · Cited by 486 · see citing works
Latent semantic sparse hashing for cross-modal similarity search
Zhou, J., Ding, G., & Guo, Y. (2014) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/2600428.2609610 · Cited by 485 · see citing works
Deep k-Nearest Neighbors: Towards Confident, Interpretable and Robust Deep LearningPreprint
Papernot, N., & McDaniel, P. D. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.04765 · Cited by 460 · see citing works
The MOPED framework: Object recognition and pose estimation for manipulation
Collet, A., Martinez, M., & Srinivasa, S. S. (2011) · The International Journal of Robotics Research · doi:10.1177/0278364911401765 · Cited by 416 · see citing works
Optimized Product Quantization for Approximate Nearest Neighbor Search
Ge, T., He, K., Ke, Q., & Sun, J. Z. (2013) · 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.2013.379 · Cited by 401 · see citing works
K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes
He, K., Wen, F., & Sun, J. (2013) · 2013 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2013.378 · Cited by 395 · see citing works
Ferroelectric ternary content-addressable memory for one-shot learning
Ni, K., Yin, X., Laguna, A. F., Joshi, S., Dünkel, S., Trentzsch, M., Müller, J., Beyer, S., Niemier, M. T., Hu, X. S., et al. (2019) · Nature Electronics · doi:10.1038/s41928-019-0321-3 · Cited by 386 · see citing works
Learning Compact Binary Descriptors with Unsupervised Deep Neural Networks
Lin, K., Lu, J., Chen, C., & Zhou, J. (2016) · 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.2016.133 · Cited by 368 · see citing works
Loda: Lightweight on-line detector of anomalies
Pevný, T. (2015) · Machine Learning · doi:10.1007/s10994-015-5521-0 · Cited by 363 · see citing works
Self-taught hashing for fast similarity search
Zhang, D., Wang, J., Cai, D., & Lu, J. (2010) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/1835449.1835455 · Cited by 363 · see citing works
Supervised Learning of Semantics-Preserving Hash via Deep Convolutional Neural Networks
Yang, H., Lin, K., & Chen, C. (2017) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2666812 · Cited by 339 · see citing works
Deep Representation Learning for Trajectory Similarity Computation
Li, X., Zhao, K., Cong, G., Jensen, C. S., & Wei, W. (2018) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2018.00062 · Cited by 302 · see citing works
Column Sampling Based Discrete Supervised Hashing
Kang, W.-C., Li, W.-J., & Zhou, Z. (2016) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v30i1.10176 · Cited by 299 · see citing works
Locality sensitive hashing: A comparison of hash function types and querying mechanisms
Paulevé, L., Jeǵou, H., & Amsaleg, L. (2010) · Pattern Recognition Letters · doi:10.1016/j.patrec.2010.04.004 · Cited by 298 · see citing works
Learning to Remember Rare EventsPreprint
Kaiser, Ł., Nachum, O., Roy, A., & Samy Bengio, A. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1703.03129 · Cited by 296 · see citing works
Multibiometric Cryptosystems Based on Feature-Level Fusion
Nagar, A., Nandakumar, K., & Jain, A. K. (2011) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2011.2166545 · Cited by 285 · see citing works
Asymmetric Deep Supervised Hashing
Jiang, Q.-Y., & Li, W.-J. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11814 · Cited by 281 · see citing works
Supervised hashing with latent factor models
Zhang, P., Zhang, W., Li, W.-J., & Guo, M. (2014) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/2600428.2609600 · Cited by 276 · see citing works
Supervised Hash Coding With Deep Neural Network for Environment Perception of Intelligent Vehicles
Yan, C. C., Xie, H., Yang, D., Yin, J. P., Zhang, Y., & Dai, Q. (2017) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2017.2749965 · Cited by 248 · see citing works
Supervised Matrix Factorization Hashing for Cross-Modal Retrieval
Tang, J., Wang, K., & Shao, L. (2016) · IEEE Transactions on Image Processing · doi:10.1109/tip.2016.2564638 · Cited by 245 · see citing works
A contextual dissimilarity measure for accurate and efficient image search
Jeǵou, H., Harzallah, H., & Schmid, C. (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.382970 · Cited by 242 · see citing works
A Survey on Deep Hashing Methods
Luo, X., Wang, H., Wu, D., Chen, C., Deng, M., Huang, J., & Hua, X.-S. (2023) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3532624 · Cited by 241 · see citing works
Sieve algorithms for the shortest vector problem are practical
Nguyễn, P. Q., & Vidick, T. (2008) · Journal of Mathematical Cryptology · doi:10.1515/jmc.2008.009 · Cited by 234 · see citing works
Quality and efficiency in high dimensional nearest neighbor search
Tao, Y., Yi, K., Sheng, C., & Kalnis, P. (2009) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1559845.1559905 · Cited by 230 · see citing works
Triguero, I., García-Gil, D., Maillo, J., Luengo, J., García, S., & Herrera, F. (2018) · WIREs Data Mining Knowl. Discov. · doi:10.1002/widm.1289 · Cited by 190 · see citing works
Deep Supervised Hashing with Triplet Labels
Wang, X., Shi, Y., & Kitani, K. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-54181-5_5 · Cited by 220 · see citing works
Hierarchical semantic indexing for large scale image retrieval
Deng, J., Berg, A. C., & Fei-Fei, L. (2011) · 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.2011.5995516 · Cited by 213 · see citing works
Composite hashing with multiple information sources
Zhang, D., Wang, F., & Si, L. (2011) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/2009916.2009950 · Cited by 213 · see citing works
Computational Health Informatics in the Big Data Age: A Survey
Fang, R., Pouyanfar, S., Yang, Y., Chen, S.-C., & Iyengar, S. S. (2017) · ACM Computing Surveys · doi:10.1145/2932707 · Cited by 210 · see citing works
Improved Consistent Sampling, Weighted Minhash and L1 Sketching
Ioffe, S. (2010) · Proceedings · doi:10.1109/icdm.2010.80 · Cited by 199 · see citing works
Towards Privacy-Preserving Content-Based Image Retrieval in Cloud Computing
Xia, Z., Zhu, Y., Sun, X., Qin, Z., & Ren, K. (2015) · IEEE Transactions on Cloud Computing · doi:10.1109/tcc.2015.2491933 · Cited by 199 · see citing works
Recent Advance in Content-based Image Retrieval: A Literature SurveyPreprint
Zhou, W., Li, H., & Tian, Q. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.06064 · Cited by 199 · see citing works
Pest24: A large-scale very small object data set of agricultural pests for multi-target detection
Wang, Q.-J., Zhang, S., Dong, S., Zhang, G., Yang, J., Li, R., & Wang, H. (2020) · Computers and Electronics in Agriculture · doi:10.1016/j.compag.2020.105585 · Cited by 193 · see citing works
Optimal Data-Dependent Hashing for Approximate Near Neighbors
Andoni, A., & Razenshteyn, I. (2015) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2746539.2746553 · Cited by 189 · see citing works
Self-citationContent based image retrieval using deep learning process
Saritha, R. R., Paul, V., & Ganeshkumar, P. (2018) · Cluster Computing · doi:10.1007/s10586-018-1731-0 · Cited by 184 · see citing works
Query Specific Fusion for Image Retrieval
Zhang, S., Yang, M., Cour, T., Yu, K., & Metaxas, D. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33709-3_47 · Cited by 183 · see citing works
Multimodal Similarity-Preserving Hashing
Masci, J., Bronstein, M. M., Bronstein, A. M., & Schmidhuber, J. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.225 · Cited by 182 · see citing works
Zhao, J., Zhou, Z., Guan, Z., Zhao, W. Z., Ning, W., Qiu, G., & He, X. (2019) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3292500.3330686 · Cited by 173 · see citing works
Capturing sequence diversity in metagenomes with comprehensive and scalable probe design
Metsky, H. C., Siddle, K. J., Gladden, A. D., Qu, J., Yang, D. K., Brehio, P., Goldfarb, A., Piantadosi, A. L., Wohl, S., Carter, A., et al. (2019) · Nature Biotechnology · doi:10.1038/s41587-018-0006-x · Cited by 172 · see citing works
Introduction to the Bag of Features Paradigm for Image Classification and RetrievalPreprint
O′Hara, S., & Draper, B. A. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1101.3354 · Cited by 170 · see citing works
Query Specific Rank Fusion for Image Retrieval
Zhang, S., Yang, M., Cour, T., Yu, K., & Metaxas, D. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2014.2346201 · Cited by 169 · see citing works
Unsupervised Semantic-Preserving Adversarial Hashing for Image Search
Deng, C. D., Yang, E., Liu, T., Li, J., Liu, W., & Tao, D. (2019) · IEEE Transactions on Image Processing · doi:10.1109/tip.2019.2903661 · Cited by 169 · see citing works
Discrete Latent Factor Model for Cross-Modal Hashing
Jiang, Q.-Y., & Li, W.-J. (2019) · IEEE Transactions on Image Processing · doi:10.1109/tip.2019.2897944 · Cited by 168 · see citing works
DistillHash: Unsupervised Deep Hashing by Distilling Data Pairs
Yang, E., Liu, T., Deng, C. D., Liu, W., & Tao, D. (2019) · 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.2019.00306 · Cited by 167 · see citing works
Complementary hashing for approximate nearest neighbor search
Xu, H., Wang, J., Zhu Li, B., Zeng, G., Li, S., & Yu, N. (2011) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2011.6126424 · Cited by 164 · see citing works
Speeding up the Xbox recommender system using a euclidean transformation for inner-product spaces
Bachrach, Y., Finkelstein, Y., Gilad-Bachrach, R., Katzir, L., Koenigstein, N., Nice, N., & Paquet, U. (2014) · ACM Conference on Recommender Systems (RecSys) · doi:10.1145/2645710.2645741 · Cited by 163 · see citing works
Multidimensional Spectral Hashing
Weiss, Y., Fergus, R., & Torralba, A. B. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33715-4_25 · Cited by 156 · see citing works
Theobald, M., Siddharth, J., & Paepcke, A. (2008) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/1390334.1390431 · Cited by 155 · see citing works
Delimitrou, C., Sánchez, D., & Kozyrakis, C. (2015) · ACM Symposium on Cloud Computing (SoCC) · doi:10.1145/2806777.2806779 · Cited by 155 · see citing works
AnDarwin: Scalable Detection of Semantically Similar Android Applications
Crussell, J., Gibler, C., & Chen, H. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40203-6_11 · Cited by 153 · see citing works
Composite Correlation Quantization for Efficient Multimodal Retrieval
Long, M., Cao, Y., Wang, J., & Yu, P. S. (2016) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/2911451.2911493 · Cited by 146 · see citing works
Discriminative coupled dictionary hashing for fast cross-media retrieval
Zhou, Y., Wu, F. Q., Yang, Y., Tian, Q., Luo, J., & Zhuang, Y. (2014) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/2600428.2609563 · Cited by 144 · see citing works
Tenney, I., Wexler, J., Bastings, J., Bolukbasi, T., Coenen, A., Gehrmann, S., Jiang, E., Pushkarna, M., Radebaugh, C., Reif, E., et al. (2020) · Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations · doi:10.18653/v1/2020.emnlp-demos.15 · Cited by 138 · see citing works
Neural information retrieval: at the end of the early years
Onal, K. D., Zhang, Y., Altıngövde, İ. S., Rahman, M. M., Karagöz, P., Braylan, A., Dang, B., Chang, H.-L., Kim, H., McNamara, Q., et al. (2017) · Information Retrieval · doi:10.1007/s10791-017-9321-y · Cited by 137 · see citing works
Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
Laarhoven, T. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-47989-6_1 · Cited by 134 · see citing works
FANNG: Fast Approximate Nearest Neighbour Graphs
Harwood, B., & Drummond, T. W. (2016) · 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.2016.616 · Cited by 133 · see citing works
Spectral Hashing With Semantically Consistent Graph for Image Indexing
Li, P., Wang, M., Cheng, J., Xu, C., & Lu, H. (2012) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2012.2199970 · Cited by 132 · see citing works
Wu, F. Q., Zhou, Y., Yang, Y., Tang, S., Zhang, Y., & Zhuang, Y. (2013) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2013.2291214 · Cited by 130 · see citing works
SketchMate: Deep Hashing for Million-Scale Human Sketch Retrieval
Xu, P., Huang, Y., Yuan, T., Pang, K., Song, Y.-Z., Xiang, T., Hospedales, T. M., Ma, Z., & Guo, J. H. (2018) · 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.2018.00844 · Cited by 129 · see citing works
Deep Hashing for Scalable Image Search
Lu, J., Liong, V. E., & Zhou, J. (2017) · IEEE Transactions on Image Processing · doi:10.1109/tip.2017.2678163 · Cited by 127 · see citing works
Learning Hash Functions Using Column GenerationPreprint
Li, X., Lin, G., Shen, C., van den Hengel, A., & Dick, A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1303.0339 · Cited by 126 · see citing works
Dimension Reduction by Random Hyperplane Tessellations
Plan, Y., & Vershynin, R. (2013) · Discrete & Computational Geometry · doi:10.1007/s00454-013-9561-6 · Cited by 123 · see citing works
Efficient and accurate nearest neighbor and closest pair search in high-dimensional space
Tao, Y., Yi, K., Sheng, C., & Kalnis, P. (2010) · ACM Transactions on Database Systems · doi:10.1145/1806907.1806912 · Cited by 123 · see citing works
Fast GPU-based locality sensitive hashing for k-nearest neighbor computation
Pan, J., & Manocha, D. (2011) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/2093973.2094002 · Cited by 122 · see citing works
Adversarial Examples for Hamming Space Search
Yang, E., Liu, T., Deng, C. D., & Tao, D. (2018) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2018.2882908 · Cited by 121 · see citing works
Where Is Your Place, Visual Place Recognition?
Garg, S., Fischer, T., & Milford, M. J. (2021) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2021/603 · Cited by 121 · see citing works
Designing sensitive viral diagnostics with machine learning
Metsky, H. C., Welch, N. L., Pillai, P. P., Haradhvala, N. J., Rumker, L., Mantena, S., Zhang, Y. B., Yang, D. K., Ackerman, C. M., Weller, J., et al. (2022) · Nature Biotechnology · doi:10.1038/s41587-022-01213-5 · Cited by 119 · see citing works
Deep Discrete Supervised Hashing
Jiang, Q.-Y., Cui, X., & Li, W.-J. (2018) · IEEE Transactions on Image Processing · doi:10.1109/tip.2018.2864894 · Cited by 118 · see citing works
Super-Bit Locality-Sensitive Hashing
Ji, J., Li, J., Yan, S., Zhang, B., & Tian, Q. (2012) · Cited by 116 · see citing works
Learning to Hash With Optimized Anchor Embedding for Scalable Retrieval
Guo, Y., Ding, G., Liu, L., Han, J., & Shao, L. (2017) · IEEE Transactions on Image Processing · doi:10.1109/tip.2017.2652730 · Cited by 108 · see citing works
Transfer Hashing: From Shallow to Deep
Zhou, J. T., Zhao, H., Peng, X., Fang, M., Qin, Z., & Goh, R. S. M. (2018) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2018.2827036 · Cited by 108 · see citing works
Beyond Locality–Sensitive Hashing
Andoni, A., Indyk, P., Ên, H. L. N., & Razenshteyn, I. (2013) · Cited by 105 · see citing works
Self-citationCoherent Semantic-Visual Indexing for Large-Scale Image Retrieval in the Cloud
Hong, R., Li, L., Cai, J., Tao, D., Wang, M., & Tian, Q. (2017) · IEEE Transactions on Image Processing · doi:10.1109/tip.2017.2710635 · Cited by 104 · see citing works
μ Suite: A Benchmark Suite for Microservices
Sriraman, A., & Wenisch, T. F. (2018) · IEEE International Symposium on Workload Characterization · doi:10.1109/iiswc.2018.8573515 · Cited by 104 · see citing works
Random Forest Based Feature Induction
Vens, C., & Costa, F. (2011) · Proceedings · doi:10.1109/icdm.2011.121 · Cited by 102 · see citing works
A Privacy-Preserving Framework for Large-Scale Content-Based Information Retrieval
Weng, L., Amsaleg, L., Morton, A., & Marchand‐Maillet, S. (2014) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2014.2365998 · Cited by 100 · see citing works
Deep Multiscale Fusion Hashing for Cross-Modal Retrieval
Nie, X., Wang, B., Li, J., Hao, F., Jian, M., & Yin, Y. (2020) · IEEE Transactions on Circuits and Systems for Video Technology · doi:10.1109/tcsvt.2020.2974877 · Cited by 99 · see citing works
A Survey on Nearest Neighbor Search Methods
RezaAbbasifard, M., Ghahremani, B., & Naderi, H. (2014) · International Journal of Computer Applications · doi:10.5120/16754-7073 · Cited by 97 · see citing works
Binary Code Ranking with Weighted Hamming Distance
Zhang, L., Zhang, Y., Tang, J., Lü, K., & Tian, Q. (2013) · 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.2013.208 · Cited by 97 · see citing works
Correlation Autoencoder Hashing for Supervised Cross-Modal Search
Cao, Y., Long, M., Wang, J., & Zhu, H. (2016) · International Conference on Multimedia Retrieval · doi:10.1145/2911996.2912000 · Cited by 96 · see citing works
Deep Ordinal Hashing With Spatial Attention
Jin, L., Shu, X., Li, K., Li, Z., Qi, G.-J., & Tang, J. (2018) · IEEE Transactions on Image Processing · doi:10.1109/tip.2018.2883522 · Cited by 94 · see citing works
- Authors
- Andoni, A., & Indyk, P.
- Affiliations
- Massachusetts Institute of Technology (US)
- Venue
- 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
- Publisher
- IEEE
- Published
- 2006
- Pages
- 459-468
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2145065594
- Cited by
- 1,067
- References
- 47
- Citations by year
- 2026: 3 · 2025: 21 · 2024: 21 · 2023: 22 · 2022: 44 · 2021: 77 · 2020: 87 · 2019: 82 · 2018: 108 · 2017: 95 · 2016: 85 · 2015: 99 · 2014: 90 · 2013: 49 · 2012: 50
- FWCI
- 16.14
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- Annual Symposium on Foundations of Computer Science (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Image and Video Retrieval Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- approximate nearest neighbor search, hash algorithms, high-dimensional Euclidean space, query response time, space complexity, lower bounds, space-efficient data structures, bounded distance decoding, Leech lattice, lattice-based 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