The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
On the resemblance and containment of documents
Abstract
Given two documents A and B we define two mathematical notions: their resemblance r(A, B) and their containment c(A, B) that seem to capture well the informal notions of "roughly the same" and "roughly contained." The basic idea is to reduce these issues to set intersection problems that can be easily evaluated by a process of random sampling that can be done independently for each document. Furthermore, the resemblance can be evaluated using a fixed size sample for each document. This paper discusses the mathematical properties of these measures and the efficient implementation of the sampling process using Rabin (1981) fingerprints.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Spencer, J. (1991) · Medical Entomology and Zoology · Cited by 4,310
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
Self-citationMin-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-citationFinding similar files in a large file system
Manber, U. (1994) · Cited by 594
Copy detection mechanisms for digital documents
Brin, S., Davis, J., & García-Molina, H. (1995) · Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95 · doi:10.1145/223784.223855 · Cited by 479
Min-wise independent permutations (extended abstract)
Broder, A. Z., Charikar, M., Frieze, A. M., & Mitzenmacher, M. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276781 · Cited by 364
Self-citation(1995) · Cited by 296
Some applications of Rabin’s fingerprinting method
Broder, A. Z. (1993) · Sequences II · doi:10.1007/978-1-4613-9323-8_11 · Cited by 204
Self-citationBuilding a scalable and accurate copy detection mechanism
Shivakumar, N., & Garcia-Molina, H. (1996) · Proceedings of the first ACM international conference on Digital libraries - DL '96 · doi:10.1145/226931.226961 · Cited by 160
Research works printed but not linked: 2
- rabin, 1981, Fingerprinting by random polynomials
- heintze, 1996, Scalable Document Fingerprinting, Proceedings of the Second Usenix Workshop on Electronic Commerce
Cited by
Canu: scalable and accurate long-read assembly via adaptive k -mer weighting and repeat separation
Koren, S., Walenz, B. P., Berlin, K., Miller, J. R., Bergman, N. H., & Phillippy, A. M. (2017) · Genome Research · doi:10.1101/gr.215087.116 · Cited by 7,304
High throughput ANI analysis of 90K prokaryotic genomes reveals clear species boundaries
Jain, C., Rodriguez-R, L. M., Phillippy, A. M., Konstantinidis, K. T., & Aluru, S. (2018) · Nature Communications · doi:10.1038/s41467-018-07641-9 · Cited by 5,748
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
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
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
Similarity estimation techniques from rounding algorithms
Charikar, M. S. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509965 · Cited by 2,220
Huang, L., Yu, W., Ma, W., Zhong, W., Feng, Z., Wang, H., Chen, Q., Peng, W., Feng, X., Qin, B., et al. (2025) · ACM Transactions on Information Systems · doi:10.1145/3703155 · Cited by 4,688
PacBio Sequencing and its Applications
Rhoads, A., & Au, K. F. (2015) · Genomics, Proteomics & Bioinformatics · doi:10.1016/j.gpb.2015.08.002 · Cited by 2,135
Jindal, N., & Liu, B. (2008) · Proceedings of the international conference on Web search and web data mining - WSDM '08 · doi:10.1145/1341531.1341560 · Cited by 1,542
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
Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences
Li, H. (2016) · Bioinformatics · doi:10.1093/bioinformatics/btw152 · Cited by 1,508
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
Schleimer, S., S, W. D., & Aiken, A. (2003) · Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data · doi:10.1145/872757.872770 · Cited by 1,099
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
Andoni, A., & Indyk, P. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.49 · Cited by 1,067
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
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
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-citationA low-bandwidth network file system
Muthitacharoen, A., Chen, B., & Mazières, D. (2001) · Proceedings of the eighteenth ACM symposium on Operating systems principles · doi:10.1145/502034.502052 · Cited by 784
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007) · Discrete Mathematics & Theoretical Computer Science · doi:10.46298/dmtcs.3545 · Cited by 695
Smart Cities: A Survey on Data Management, Security, and Enabling Technologies
Gharaibeh, A., Salahuddin, M. A., Hussini, S. J., Khreishah, A., Khalil, I., Guizani, M., & Al-Fuqaha, A. (2017) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2017.2736886 · Cited by 628
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
Enquiring Minds: Early Detection of Rumors in Social Media from Enquiry Posts
Zhao, Z., Resnick, P., & Mei, Q. (2015) · Proceedings of the 24th International Conference on World Wide Web · doi:10.1145/2736277.2741637 · Cited by 583
Nanopore sequencing and the Shasta toolkit enable efficient de novo assembly of eleven human genomes
Shafin, K., Pesout, T., Lorig-Roach, R., Haukness, M., Olsen, H. E., Bosworth, C., Armstrong, J., Tigyi, K., Maurer, N., Koren, S., et al. (2020) · Nature Biotechnology · doi:10.1038/s41587-020-0503-6 · Cited by 567
Assembly of 913 microbial genomes from metagenomic sequencing of the cow rumen
Stewart, R. D., Auffret, M. D., Warr, A., Wiser, A. H., Press, M. O., Langford, K. W., Liachko, I., Snelling, T. J., Dewhurst, R. J., Walker, A. W., et al. (2018) · Nature Communications · doi:10.1038/s41467-018-03317-6 · Cited by 559
A review of methods and databases for metagenomic classification and assembly
Breitwieser, F. P., Lu, J., & Salzberg, S. L. (2019) · Briefings in Bioinformatics · doi:10.1093/bib/bbx120 · Cited by 566
Time- and memory-efficient genome assembly with Raven
Vaser, R., & Šikić, M. (2021) · Nature Computational Science · doi:10.1038/s43588-021-00073-4 · Cited by 522
Learning 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
PLSDB: a resource of complete bacterial plasmids
Galata, V., Fehlmann, T., Backes, C., & Keller, A. (2019) · Nucleic Acids Research · doi:10.1093/nar/gky1050 · Cited by 470
Near Duplicate Image Detection: min-Hash and tf-idf Weighting
Chum, O., Philbin, J., & Zisserman, A. (2008) · Procedings of the British Machine Vision Conference 2008 · doi:10.5244/c.22.50 · Cited by 460
Robust and efficient fuzzy match for online data cleaning
Chaudhuri, S., Ganjam, K., Ganti, V., & Motwani, R. (2003) · Proceedings of the 2003 ACM SIGMOD international conference on Management of data · doi:10.1145/872757.872796 · Cited by 457
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
Jindal, N., & Liu, B. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242759 · Cited by 449
Fast and flexible bacterial genomic epidemiology with PopPUNK
Lees, J. A., Harris, S. R., Tonkin-Hill, G., Gladstone, R. A., Lo, S. W., Weiser, J. N., Corander, J., Bentley, S. D., & Croucher, N. J. (2019) · Genome Research · doi:10.1101/gr.241455.118 · Cited by 438
Mandera, P., Keuleers, E., & Brysbaert, M. (2017) · Journal of Memory and Language · doi:10.1016/j.jml.2016.04.001 · Cited by 428
Identifying and Filtering Near-Duplicate Documents
Broder, A. Z. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-45123-4_1 · Cited by 395
Self-citationDifferentially 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
Min-wise independent permutations (extended abstract)
Broder, A. Z., Charikar, M., Frieze, A. M., & Mitzenmacher, M. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276781 · Cited by 364
Self-citationLSH forest: self-tuning indexes for similarity search
Bawa, M., Condie, T., & Ganesan, P. (2005) · Proceedings of the 14th international conference on World Wide Web - WWW '05 · doi:10.1145/1060745.1060840 · Cited by 353
Finding interesting associations without support pruning
Cohen, E., Datar, M., Fujiwara, S., Gionis, A., Indyk, P., Motwani, R., Ullman, J. D., & Yang, C. (2001) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.908981 · Cited by 341
Kernelized 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
Extreme Binning: Scalable, parallel deduplication for chunk-based file backup
Bhagwat, D., Eshghi, K., Long, D. D. E., & Lillibridge, M. (2009) · 2009 IEEE International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems · doi:10.1109/mascot.2009.5366623 · Cited by 325
Mash Screen: high-throughput sequence containment estimation for genome discovery
Ondov, B. D., Starrett, G. J., Sappington, A., Kostic, A., Koren, S., Buck, C. B., & Phillippy, A. M. (2019) · Genome Biology · doi:10.1186/s13059-019-1841-x · Cited by 320
Efficient semi-streaming algorithms for local triangle counting in massive graphs
Becchetti, L., Boldi, P., Castillo, C., & Gionis, A. (2008) · Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1401890.1401898 · Cited by 319
A Comprehensive Study of the Past, Present, and Future of Data Deduplication
Xia, W., Jiang, H., Feng, D., Douglis, F., Shilane, P., Hua, Y., Fu, M., Zhang, Y., & Zhou, Y. (2016) · Proceedings of the IEEE · doi:10.1109/jproc.2016.2571298 · Cited by 318
Challenges in web search engines
Henzinger, M. R., Motwani, R., & Silverstein, C. (2002) · ACM SIGIR Forum · doi:10.1145/792550.792553 · Cited by 307
Deduplicating Training Data Makes Language Models Better
Lee, K., Ippolito, D., Nystrom, A., Zhang, C., Eck, D., Callison-Burch, C., & Carlini, N. (2022) · Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2022.acl-long.577 · Cited by 304
A protocol-independent technique for eliminating redundant network traffic
Spring, N. T., & Wetherall, D. (2000) · ACM SIGCOMM Computer Communication Review · doi:10.1145/347057.347408 · Cited by 303
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
Visualization of very large high-dimensional data sets as minimum spanning trees
Probst, D., & Reymond, J.-L. (2020) · Journal of Cheminformatics · doi:10.1186/s13321-020-0416-x · Cited by 295
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
Detection of review spam: A survey
Heydari, A., Tavakoli, M. A., Salim, N., & Heydari, Z. (2015) · Expert Systems with Applications · doi:10.1016/j.eswa.2014.12.029 · Cited by 290
Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments
Fogaras, D., Rácz, B., Csalogány, K., & Sarlós, T. (2005) · Internet Mathematics · doi:10.1080/15427951.2005.10129104 · Cited by 282
Web-scale distributional similarity and entity set expansion
Pantel, P., Crestan, E., Borkovsky, A., Popescu, A.-M., & Vyas, V. (2009) · Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing Volume 2 - EMNLP '09 · doi:10.3115/1699571.1699635 · Cited by 271
A survey of Twitter research: Data model, graph structure, sentiment analysis and attacks
Antonakaki, D., Fragopoulou, P., & Ioannidis, S. (2021) · Expert Systems with Applications · doi:10.1016/j.eswa.2020.114006 · Cited by 265
TimeLMs: Diachronic Language Models from Twitter
Loureiro, D., Barbieri, F., Neves, L., Espinosa Anke, L., & Camacho-collados, J. (2022) · Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics: System Demonstrations · doi:10.18653/v1/2022.acl-demo.25 · Cited by 263
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
Huang, L., Yu, W., Ma, W., Zhong, W., Feng, Z., Wang, H., Chen, Q., Peng, W., Feng, X., Qin, B., et al. (2023) · arXiv · doi:10.48550/arxiv.2311.05232 · Cited by 2,516
“Furthermore, MinHash (Broder, 1997) stands out as a prevalent algorithm for large-scale deduplication tasks (Gyawali et al., 2020).”
From Matching to Generation: A Survey on Generative Information Retrieval
Li, X., Jin, J., Zhou, Y., Zhang, Y., Zhang, P., Zhu, Y., & Dou, Z. (2025) · ACM Transactions on Information Systems · doi:10.1145/3722552 · Cited by 172
Unifying the known and unknown microbial coding sequence space
Vanni, C., Schechter, M. S., Acinas, S. G., Barberán, A., Buttigieg, P. L., Casamayor, E. O., Delmont, T. O., Duarte, C. M., Eren, A. M., Finn, R. D., et al. (2022) · eLife · doi:10.7554/elife.67667 · Cited by 134
Grauman, K., & Leibe, B. (2011) · Synthesis Lectures on Artificial Intelligence and Machine Learning · doi:10.2200/s00332ed1v01y201103aim011 · Cited by 126
Towards Scaling Fully Personalized PageRank
Fogaras, D., & Rácz, B. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30216-2_9 · Cited by 84
Algorithmic Challenges in Web Search Engines
Henzinger, M. R. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129079 · Cited by 81
Off the Beaten Path: Let's Replace Term-Based Retrieval with k-NN Search
Boytsov, L., Novak, D., Malkov, Y., & Nyberg, E. (2016) · Proceedings of the 25th ACM International on Conference on Information and Knowledge Management · doi:10.1145/2983323.2983815 · Cited by 50
Copy detection in Chinese documents using Ferret
Bao, J. P., Lyon, C., & Lane, P. C. R. (2007) · Language Resources and Evaluation · doi:10.1007/s10579-007-9020-1 · Cited by 19
Are Large Language Models Memorizing Bug Benchmarks?
Ramos, D., Mamede, C., Jain, K., Canelas, P., Gamboa, C., & Goues, C. L. (2024) · arXiv · doi:10.48550/arxiv.2411.13323 · Cited by 16
KHyperLogLog: 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
Fraud De-Anonymization for Fun and Profit
Hernandez, N., Rahman, M., Recabarren, R., & Carbunar, B. (2018) · Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3243734.3243770 · Cited by 16
Public Attitudes Toward ChatGPT on Twitter: Sentiments, Topics, and Occupations
Koonchanok, R., Pan, Y., & Jang, H. (2023) · arXiv · doi:10.48550/arxiv.2306.12951 · Cited by 5
Kawano, T., Shiraishi, T., Kuzuyama, T., & Umemura, M. (2026) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1013181 · Cited by 3
MiMo: Unlocking the Reasoning Potential of Language Model - From Pretraining to Posttraining
Xiaomi, L.-C., :, Xia, B., Shen, B., Cici, Zhu, D., Zhang, D., Wang, G., Zhang, H., Liu, H., et al. (2025) · arXiv · doi:10.48550/arxiv.2505.07608 · Cited by 1
“We adopt both URL deduplication and MinHash deduplication (Broder, 1997) across all webpage dumps.”
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].”
Self-Improvement of Large Language Models: A Technical Overview and Future Outlook
Yang, H., Xerri, M., Park, S., Zhang, H., Feng, Y., Kogilathota, S. A., & Zhou, J. (2026) · arXiv · doi:10.48550/arxiv.2603.25681
Grattafiori, A., Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Vaughan, A., et al. (2024) · arXiv · doi:10.48550/arxiv.2407.21783 · Cited by 505
Metadata
- Authors
- Broder, A. Z.
- Venue
- Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No.97TB100171)
- Publisher
- IEEE Comput. Soc
- Published
- 2002-11-22
- Pages
- 21-29
- OpenAlex
- W2132069633
- Cited by
- 1,698
- References
- 9
- FWCI
- 25.28
- 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.