paper

On the resemblance and containment of documents

  • Authors:
Read the paper

📜 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 fingerprints.

✨ Summary

  • The paper represents documents as sets of contiguous token subsequences, or w-shingles. It defines resemblance as the Jaccard coefficient, ( S(A,w)\cap S(B,w) / S(A,w)\cup S(B,w) ), and containment of A in B as ( S(A,w)\cap S(B,w) / S(A,w) ).
  • It shows that these quantities can be estimated from independently computed document sketches. A fixed-size minimum sample supports resemblance estimation, while a modulus-based sample supports both resemblance and containment estimation. Rabin fingerprints provide an efficient implementation, including sliding-window computation.
  • The paper reports a large-scale experiment over more than 30 million Web documents, using the method to create clusters of syntactically similar documents. The reported experiment produced 3.6 million clusters containing 12.3 million documents.
  • Its main subsequent influence was the development and formal study of MinHash and min-wise independent permutations. Later work explicitly identifies the paper as introducing set MinHash for estimating Jaccard similarity, while the related 2000 paper formalized min-wise independent permutation families. (cs.princeton.edu)
  • The approach also underlies practical near-duplicate and Web-document clustering systems, including the authors’ subsequent Syntactic Clustering of the Web, which applied the method to the Web and described applications such as search-result filtering and duplicate-document detection. (ambuehler.ethz.ch)
  • The same resemblance and containment framework has continued to be used and extended in other fields, including metagenomic analysis, where later research compares classical MinHash with containment-oriented estimators. (sciencedirect.com)