--- title: "Detecting Near-Duplicates for Web Crawling — Manku 2007" description: "Web crawlers often fetch pages whose main content matches a page already stored, differing only in minor parts… Cited by 27 papers here." authors: ["Gurmeet Singh Manku", "Arvind Jain", "Anish Das Sarma"] year: 2007 venue: "WWW 2007" source: "https://research.google/pubs/detecting-near-duplicates-for-web-crawling/" doi: "10.1145/1242572.1242592" licence: "author's copy (Google Research) — read only" summary_licence: "Elamur Cosmic License" canonical: "https://research.elamur.ai/free/en/papers/manku-2007-detecting-near-duplicates-web/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/manku-2007-detecting-near-duplicates-web/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2007](https://md.research.elamur.ai/free/en/papers/2007/) / Detecting Near-Duplicates for Web Crawling # Detecting Near-Duplicates for Web Crawling **Authors:** Gurmeet Singh Manku, Arvind Jain and Anish Das Sarma · **Year:** 2007 · **Venue:** [WWW 2007](https://md.research.elamur.ai/free/en/venues/international-world-wide-web-conference-www/) ([WWW 2007](https://md.research.elamur.ai/free/en/venues/international-world-wide-web-conference-www/2007/)) · **Licence:** author's copy (Google Research) — read only **Links:** [Publisher's page](https://doi.org/10.1145/1242572.1242592) · [PDF](https://research.google.com/pubs/archive/33026.pdf) · [DOI 10.1145/1242572.1242592](https://doi.org/10.1145/1242572.1242592) · [OpenAlex](https://openalex.org/W2145349611) **Citations:** 610 citations (OpenAlex, 2026-10-14) · [27](https://md.research.elamur.ai/free/en/papers/manku-2007-detecting-near-duplicates-web/cited-by/) in our library, of the 149,439 papers whose bibliographies we read ## Summary Web crawlers often fetch pages whose main content matches a page already stored, differing only in minor parts such as ads, counters or timestamps. Exact checksums cannot catch these near-duplicates. Skipping them, along with their outgoing links, saves bandwidth and storage, improves index quality and reduces load on remote servers. The obstacle is scale: billions of stored pages and billions of new fetches per day, with decisions needed quickly on few machines. The authors, working at Google, make two contributions. First, they apply Charikar's simhash to web pages. Weighted features from standard IR preprocessing are compressed into a short fingerprint, and pages with similar content end up with fingerprints that differ in only a few bits. Experiments on a repository of 8B pages support 64-bit fingerprints with a threshold of k = 3 differing bits. Second, they solve the resulting Hamming Distance Problem. They keep several sorted, compressed copies of the fingerprint table, each with its bits reordered by a different permutation. A query probes these tables in parallel by matching leading bits, then checks the few candidates found. This works for single online lookups and for large batches. The paper also surveys earlier duplicate-detection methods. ## Key points - **How simhash works:** each feature's hash adds or subtracts that feature's weight across f counters. The sign of each counter then gives the corresponding fingerprint bit. Unlike SHA-1 or MD5, similar inputs produce nearby hash values. - **Target workload:** 8B 64-bit fingerprints, about 64GB in total. - Online queries must be answered within milliseconds for k = 3. - Batch mode handles about 1M queries in roughly 100 seconds, which is about 1B queries per day. - **Why simple approaches fail:** probing every fingerprint within distance 3 would take 41,664 lookups per query. Precomputing all such neighbours would multiply storage by up to that factor. The permuted-table design sits between these extremes and allows a trade-off between query time and memory. - **Fingerprint size:** simhash needs only 8 bytes per page, compared with 24 bytes for Broder's shingle-based fingerprints. The authors used Charikar's original C++ implementation, and Henzinger (SIGIR 2006) compared the two methods. - **Practical use:** in a real crawler, a near-duplicate signal may serve as one factor in a URL's crawl priority rather than a strict keep-or-drop rule. *Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.* ## Institutions - [Google](https://md.research.elamur.ai/free/en/companies/google/) — Company, Mountain View, United States · 533 works · 443,884 citations - [Stanford University](https://md.research.elamur.ai/free/en/universities/stanford-university/) — University, Stanford, United States · 567 works · 335,189 citations 📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 19,503 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 18,805 works · [🗄️ Information Systems](https://md.research.elamur.ai/free/en/shelves/computer-science/information-systems/) · 1,888 works · [🎯 Decision Sciences](https://md.research.elamur.ai/free/en/shelves/decision-sciences/) · 306 works · [🎯 Management Science and Operations Research](https://md.research.elamur.ai/free/en/shelves/decision-sciences/management-science-and-operations-research/) · 145 works ## Cite Cite as: Gurmeet Singh Manku, Arvind Jain and Anish Das Sarma. 2007. Detecting Near-Duplicates for Web Crawling. WWW 2007. The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @inproceedings{manku2007detecting, title = {{Detecting Near-Duplicates for Web Crawling}}, author = {Gurmeet Singh Manku, Arvind Jain and Anish {Das Sarma}}, booktitle = {WWW 2007}, year = {2007}, doi = {10.1145/1242572.1242592}, url = {https://doi.org/10.1145/1242572.1242592} } ``` - [← previous Factored Translation Models](https://md.research.elamur.ai/free/en/papers/koehn-2007-factored-translation-models/) - [next → Wide-Coverage Efficient Statistical Parsing with CCG and Log-Linear Models](https://md.research.elamur.ai/free/en/papers/clark-2007-wide-coverage-efficient-statistical-parsing/) - [↑ back to papers of 2007](https://md.research.elamur.ai/free/en/papers/2007/) *Updated 3 November 2026*