Similarity estimation techniques from rounding algorithms
The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
Abstract
A locality sensitive hashing scheme is a distribution on a family F of hash functions operating on a collection of objects, such that for two objects x, y, Prh∈F[h(x) = h(y)] = sim(x,y), where sim(x,y) ∈ [0, 1] is some similarity function defined on the collection of objects. Such a scheme leads to a compact representation of objects so that similarity of objects can be estimated from their compact sketches, and also leads to efficient algorithms for approximate nearest neighbor search and clustering. Min-wise independent permutations provide an elegant construction of such a locality sensitive hashing scheme for a collection of subsets with the set similarity measure sim(A, B) = |A∩B| |A∪B |. We show that rounding algorithms for LPs and SDPs used in the context of approximation algorithms can be viewed as locality sensitive hashing schemes for several interesting collections of objects. Based on this insight, we construct new locality sensitive hashing schemes for: 1. A collection of vectors with the distance between ⃗u and ⃗v measured by θ(⃗u,⃗v)/π, where θ(⃗u,⃗v) is the angle between ⃗u and ⃗v. This yields a sketching scheme for estimating the cosine similarity measure between two vectors, as well as a simple alternative to minwise independent permutations for estimating set similarity. 2. A collection of distributions on n points in a metric space, with distance between distributions measured by the Earth Mover Distance (EMD), (a popular distance measure in graphics and vision). Our hash functions map distributions to points in the metric space such that, for distributions P and Q,
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
The Earth Mover's Distance as a Metric for Image Retrieval
Rubner, Y., Tomasi, C., & Guibas, L. J. (2000) · International Journal of Computer Vision · doi:10.1023/a:1026543900054 · Cited by 4,568
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
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
(1999) · Cited by 3,186
A metric for distributions with applications to image databases
Rubner, Y., Tomasi, C., & Guibas, L. J. (2002) · Sixth International Conference on Computer Vision (IEEE Cat. No.98CH36271) · doi:10.1109/iccv.1998.710701 · Cited by 1,726
On the resemblance and containment of documents
Broder, A. Z. (2002) · Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No.97TB100171) · doi:10.1109/sequen.1997.666900 · Cited by 1,698
Syntactic clustering of the Web
Broder, A. Z., 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,343
The Space Complexity of Approximating the Frequency Moments
Alon, N., Matias, Y., & Szegedy, M. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1545 · Cited by 1,140
Min-Wise Independent Permutations
Broder, A. Z., Charikar, M., Frieze, A. M., & Mitzenmacher, M. (2000) · Journal of Computer and System Sciences · doi:10.1006/jcss.1999.1690 · Cited by 802
Self-citationProbabilistic approximation of metric spaces and its algorithmic applications
Bartal, Y. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548477 · Cited by 635
Cited by
From Frequency to Meaning: Vector Space Models of Semantics
Turney, P. D., & Pantel, P. (2010) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2934 · Cited by 2,866
Rajaraman, A., & Ullman, J. D. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9781139058452 · Cited by 2,262
Google news personalization: scalable online collaborative filtering
Das, A. S., Datar, M., Garg, A., & Rajaram, S. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242610 · Cited by 1,511
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
Efficient integration of heterogeneous single-cell transcriptomes using Scanorama
Hie, B., Bryson, B., & Berger, B. (2019) · Nature Biotechnology · doi:10.1038/s41587-019-0113-3 · Cited by 974
Wang, J., Zhang, T., Song, J., Sebe, N., & Shen, H. T. (2018) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2699960 · Cited by 971
Supervised Hashing for Image Retrieval via Image Representation Learning
Xia, R., Pan, Y., Lai, H., Liu, C., & Yan, S. (2014) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v28i1.8952 · Cited by 952
Assembling large genomes with single-molecule sequencing and locality-sensitive hashing
Berlin, K., Koren, S., Chin, C.-S., Drake, J. P., Landolin, J. M., & Phillippy, A. M. (2015) · Nature Biotechnology · doi:10.1038/nbt.3238 · Cited by 934
Kernelized locality-sensitive hashing for scalable image search
Kulis, B., & Grauman, K. (2009) · 2009 IEEE 12th International Conference on Computer Vision · doi:10.1109/iccv.2009.5459466 · Cited by 890
FastText.zip: Compressing text classification models
Joulin, A., Grave, E., Bojanowski, P., Douze, M., Jégou, H., & Mikolov, T. (2016) · arXiv · doi:10.48550/arxiv.1612.03651 · Cited by 887
Large-scale image retrieval with compressed Fisher vectors
Perronnin, F., Liu, Y., Sanchez, J., & Poirier, H. (2010) · 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2010.5540009 · Cited by 761
Scaling up all pairs similarity search
Bayardo, R. J., Ma, Y., & Srikant, R. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242591 · Cited by 673
Efficient k-nearest neighbor graph construction for generic similarity measures
Dong, W., Moses, C., & Li, K. (2011) · Proceedings of the 20th international conference on World wide web · doi:10.1145/1963405.1963487 · Cited by 673
Distributed large-scale natural graph factorization
Ahmed, A., Shervashidze, N., Narayanamurthy, S., Josifovski, V., & Smola, A. J. (2013) · Proceedings of the 22nd international conference on World Wide Web · doi:10.1145/2488388.2488393 · Cited by 648
Very sparse random projections
Li, P., Hastie, T. J., & Church, K. W. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150436 · Cited by 621
Detecting near-duplicates for web crawling
Manku, G. S., Jain, A., & Das Sarma, A. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242592 · Cited by 617
Efficient Deep Learning: A Survey on Making Deep Learning Models Smaller, Faster, and Better
Menghani, G. (2023) · ACM Computing Surveys · doi:10.1145/3578938 · Cited by 605
On the performance of ConvNet features for place recognition
Sunderhauf, N., Shirazi, S., Dayoub, F., Upcroft, B., & Milford, M. (2015) · 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2015.7353986 · Cited by 544
Exploration in deep reinforcement learning: A survey
Ladosz, P., Weng, L., Kim, M., & Oh, H. (2022) · Information Fusion · doi:10.1016/j.inffus.2022.03.003 · Cited by 525
“Here, a technique called SimHash [63] was used, which rep-”
MethodLearning to Hash for Indexing Big Data—A Survey
Wang, J., Liu, W., Kumar, S., & Chang, S.-F. (2016) · Proceedings of the IEEE · doi:10.1109/jproc.2015.2487976 · Cited by 519
Douze, M., Guzhva, A., Deng, C., Johnson, J., Szilvasy, G., Mazaré, P.-E., Lomeli, M., Hosseini, L., & Jégou, H. (2026) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2025.3618474 · Cited by 478
“In particular, the cosine sketch [13] produces binary vectors such that the Hamming distance is an estimator of the cosine similarity between the original embeddings.”
Efficient similarity joins for near duplicate detection
Xiao, C., Wang, W., Lin, X., & Yu, J. X. (2008) · Proceedings of the 17th international conference on World Wide Web · doi:10.1145/1367497.1367516 · Cited by 455
Finding near-duplicate web pages: a large-scale evaluation of algorithms
Henzinger, M. (2006) · Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/1148170.1148222 · Cited by 421
Anomaly detection in dynamic networks: a survey
Ranshous, S., Shen, S., Koutra, D., Harenberg, S., Faloutsos, C., & Samatova, N. F. (2015) · WIREs Computational Statistics · doi:10.1002/wics.1347 · Cited by 379
Differentially Private High-Dimensional Approximate Range Counting, Revisited
Wang, J., Shen, H. T., Song, J., & Ji, J. (2014) · arXiv (Cornell University) · doi:10.4230/lipics.cpm.2023.20 · Cited by 370
Efficient similarity search and classification via rank aggregation
Fagin, R., Kumar, R., & Sivakumar, D. (2003) · Proceedings of the 2003 ACM SIGMOD international conference on Management of data · doi:10.1145/872757.872795 · Cited by 362
UNICORN: Runtime Provenance-Based Detector for Advanced Persistent Threats
Han, X., Pasquier, T., Bates, A., Mickens, J., & Seltzer, M. (2020) · Proceedings 2020 Network and Distributed System Security Symposium · doi:10.14722/ndss.2020.24046 · Cited by 349
“Formally, we define LSH as follows (adopted from Charikar [25]): Definition 1: A locality sensitive hashing scheme is a distribution on a family F of hash functions operating on a collection of objects, such that for two objects m , n , where sim ( m,n ) is some similarity function defined on the…”
MethodKernelized Locality-Sensitive Hashing
Kulis, B., & Grauman, K. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.219 · Cited by 331
Efficient similarity joins for near-duplicate detection
Xiao, C., Wang, W., Lin, X., Yu, J. X., & Wang, G. (2011) · ACM Transactions on Database Systems · doi:10.1145/2000824.2000825 · Cited by 331
Automated Website Fingerprinting through Deep Learning
Rimmer, V., Preuveneers, D., Juarez, M., Goethem, T. V., & Joosen, W. (2018) · Proceedings 2018 Network and Distributed System Security Symposium · doi:10.14722/ndss.2018.23105 · Cited by 319
Visualizing Large-scale and High-dimensional Data
Tang, J., Liu, J., Zhang, M., & Mei, Q. (2016) · Proceedings of the 25th International Conference on World Wide Web · doi:10.1145/2872427.2883041 · Cited by 306
Efficient community detection in large networks using content and links
Ruan, Y., Fuhry, D., & Parthasarathy, S. (2013) · Proceedings of the 22nd international conference on World Wide Web · doi:10.1145/2488388.2488483 · Cited by 304
Malware identification using visualization images and deep learning
Ni, S., Qian, Q., & Zhang, R. (2018) · Computers & Security · doi:10.1016/j.cose.2018.04.005 · Cited by 299
Generating Phrasal and Sentential Paraphrases: A Survey of Data-Driven Methods
Madnani, N., & Dorr, B. J. (2010) · Computational Linguistics · doi:10.1162/coli_a_00002 · Cited by 298
#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning
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 296
Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs
Manzoor, E., Milajerdi, S. M., & Akoglu, L. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939783 · Cited by 291
New directions in nearest neighbor searching with applications to lattice sieving
Becker, A., Ducas, L., Gama, N., & Laarhoven, T. (2016) · Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms · doi:10.1137/1.9781611974331.ch2 · Cited by 287
Fast image search for learned metrics
Jain, P., Kulis, B., & Grauman, K. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587841 · Cited by 279
Fast search in Hamming space with multi-index hashing
Norouzi, M., Punjani, A., & Fleet, D. J. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6248043 · Cited by 263
Fast Similarity Search for Learned Metrics
Kulis, B., Jain, P., & Grauman, K. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2009.151 · Cited by 256
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
Ham, T. J., Lee, Y., Seo, S. H., Kim, S., Choi, H., Jung, S. J., & Lee, J. W. (2021) · 2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA) · doi:10.1109/isca52012.2021.00060 · Cited by 192
(2016) · Thammasat University Digital Collections · Cited by 153
Grauman, K., & Leibe, B. (2011) · Synthesis Lectures on Artificial Intelligence and Machine Learning · doi:10.2200/s00332ed1v01y201103aim011 · Cited by 126
“Early LSH functions were developed to accommodate the Hamming distance (Indyk & Motwani 1998), inner products (Charikar 2002), and ℓp norms (Datar et al. 2004).”
BackgroundInfluentialTrellis tree-based analysis reveals stromal regulation of patient-derived organoid drug responses
Ramos Zapatero, M., Tong, A., Opzoomer, J. W., O’Sullivan, R., Cardoso Rodriguez, F., Sufi, J., Vlckova, P., Nattress, C., Qin, X., Claus, J., et al. (2023) · Cell · doi:10.1016/j.cell.2023.11.005 · Cited by 72
The BigScience ROOTS Corpus: A 1.6TB Composite Multilingual Dataset
Laurençon, H., Saulnier, L., Wang, T., Akiki, C., del Moral, A. V., Scao, T. L., Von Werra, L., Mou, C., Ponferrada, E. G., Nguyen, H., et al. (2023) · arXiv · doi:10.48550/arxiv.2303.03915 · Cited by 93
Principles of hash-based text retrieval
Stein, B. (2007) · Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/1277741.1277832 · Cited by 55
CSCC: Simple, Efficient, Context Sensitive Code Completion
Asaduzzaman, M., Roy, C. K., Schneider, K. A., & Hou, D. (2014) · 2014 IEEE International Conference on Software Maintenance and Evolution · doi:10.1109/icsme.2014.29 · Cited by 55
A Survey of Exploration Methods in Reinforcement Learning
Amin, S., Gomrokchi, M., Satija, H., van Hoof, H., & Precup, D. (2021) · arXiv · doi:10.48550/arxiv.2109.00157 · Cited by 41
Representing high throughput expression profiles via perturbation barcodes reveals compound targets
Filzen, T. M., Kutchukian, P. S., Hermes, J. D., Li, J., & Tudor, M. (2017) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1005335 · Cited by 31
C4Corpus: Multilingual Web-size Corpus with Free License
Habernal, I., Zayed, O., & Gurevych, I. (2016) · Proceedings of the Language Resources and Evaluation Conference · doi:10.63317/3iti4i8msr33 · Cited by 30
“We implemented a greedy algo-rithm by employing the state-of-the-art SimHash algorithm introduced by Charikar (2002) and the bitwise hamming distance technique.”
MethodDetecting duplicate web documents using clickthrough data
Radlinski, F., Bennett, P. N., & Yilmaz, E. (2011) · Proceedings of the fourth ACM international conference on Web search and data mining · doi:10.1145/1935826.1935859 · Cited by 19
“A similar technique that combines the accuracy of similarity based methods and the efficiency of shingling was developed by Charikar [12].”
MethodInfluentialKHyperLogLog: Estimating Reidentifiability and Joinability of Large Data at Scale
Chia, P. H., Desfontaines, D., Perera, I. M., Simmons-Marengo, D., Li, C., Day, W.-Y., Wang, Q., & Guevara, M. (2019) · 2019 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2019.00046 · Cited by 15
Zhao, Z., Gao, M., Luo, F., Zhang, Y., & Xiong, Q. (2020) · 2020 International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn48605.2020.9207640 · Cited by 13
A Survey on Data Selection for Language Models
Albalak, A., Elazar, Y., Xie, S. M., Longpre, S., Lambert, N., Wang, X., Muennighoff, N., Hou, B., Pan, L., Jeong, H., et al. (2024) · arXiv · doi:10.48550/arxiv.2402.16827 · Cited by 12
SimClone: Detecting Tabular Data Clones Using Value Similarity
Yang, X., Rajbahadur, G. K., Lin, D., Wang, S., & Jiang, Z. M. (. (2025) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/3676961 · Cited by 3
SEDM: Selective Self-Evolving Distributed Memory for Agents
Liu, Y., Min, A., Wang, Y., Yao, Y., Han, Y., Zhang, R., He, J., Li, Z., Qi, Y., Xu, H., et al. (2025) · arXiv · doi:10.48550/arxiv.2509.09498 · Cited by 20
“By collapsing near-duplicates into single representatives, the repository reduces retrieval noise and strengthens utility signals [1, 26, 4, 51].”
Hippocampus: An Efficient and Scalable Memory Module for Agentic AI
Li, Y., Cao, L., Ahmed, F., Sharma, P., & Li, B. (2026) · arXiv · doi:10.48550/arxiv.2602.13594
“It is a known fact (Charikar, 2002) that for any two vectors v , w at angle θ , the probability their signs agree on a random hyperplane is Concentration (Hoeffding/Chernoff bound).”
Metadata
- Authors
- Charikar, M. S.
- Venue
- Proceedings of the thiry-fourth annual ACM symposium on Theory of computing
- Publisher
- ACM
- Published
- 2002-05-19
- Pages
- 380-388
- OpenAlex
- W2012833704
- Cited by
- 2,220
- References
- 28
- FWCI
- 3.82
- Type
- conference paper
- Language
- en
- Open access
- closed
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.