Power-Law Based Estimation of Set Similarity Join Size

Hongrae Lee, Raymond T. Ng, Kyuseok ShimPVLDB 2009 · DOI

TL;DR

This paper introduces a novel, efficient, and accurate method for estimating the size of set similarity joins (SSJoin), a crucial operation for tasks like duplicate detection and data cleaning. The approach leverages Min-Hash signatures and a new "Lattice Counting" technique, combined with the observation of power-law distributions in signature pattern frequencies, to overcome the computational challenges of traditional methods.

What Problem Does This Paper Address?

Databases often contain redundant or similar entries across various data types. Identifying pairs of records with similar content, especially when content is represented as sets (e.g., sets of words from a document, n-grams from an address), is a fundamental problem known as Set Similarity Join (SSJoin). This operation is vital for applications like near-duplicate document detection, data cleaning, and query refinement. However, accurately estimating the size of the result of an SSJoin query is critical for query optimizers to generate efficient execution plans. Traditional methods for SSJoin size estimation struggle with accuracy, scalability, or both, especially for high similarity thresholds. This paper addresses the challenge of providing an accurate and efficient SSJoin size estimation technique.

Methods

The paper proposes a multi-faceted approach:

  • Min-Hash Signatures: Sets are first represented by compact Min-Hash signatures. These signatures allow for faster similarity estimations compared to direct set comparisons.
  • Signature Patterns & Frequent Pattern Mining: The core idea is to transform the SSJoin size estimation problem into a frequent pattern mining problem on these signatures. Signature patterns are like signatures with "don't care" positions (X). Finding frequent signature patterns (those matching many sets) helps identify potential similar pairs.
  • Lattice Counting: A naive approach of summing up pairs from each frequent pattern leads to overcounting due to overlapping patterns. The paper introduces "Lattice Counting," a novel technique that structures the relationships between signature patterns and their matching sets using a lattice. This allows for accurate counting of the union of matching sets, effectively handling overlaps using an Inclusion-Exclusion principle adapted for the lattice structure.
  • Power-Law Estimation: To efficiently obtain the necessary pattern frequency distributions, especially for low minimum support thresholds (which are crucial for finding relevant patterns), the paper exploits a recently observed power-law relationship between pattern frequency and count. This allows for estimating the distribution of patterns without exhaustively mining all of them.
  • Systematic Overestimation Correction: Min-Hash signatures, while efficient, can lead to a systematic overestimation of similarity. The paper models this as a state transition problem and proposes a correction procedure using Non-Negative Least Squares (NNLS) optimization to adjust the estimated counts.

Datasets

  • DBLP Dataset: A real-world dataset consisting of 794,061 sets, used for experiments and scalability tests. Subsets of varying sizes (40K, 80K, 160K, 240K, 400K, 800K) were also used.
  • Synthetic Dataset: Generated using the IBM Quest synthetic data generator, with 50,000 sets and a universe size of 10,000. Average set sizes were varied from 15 to 50.

Key Insights and Ideas

  • SSJoin to Pattern Mining Transformation: The problem of estimating SSJoin size can be effectively reframed as mining frequent patterns in Min-Hash signatures. This shifts the focus from direct set comparisons to pattern discovery.
  • Lattice Structure for Overlap Handling: The lattice structure provides an elegant way to manage the complex overlaps between signature patterns, enabling accurate union cardinality calculations that are crucial for avoiding overestimation.
  • Power-Laws as an Estimation Tool: The observed power-law distribution in pattern frequency-count relationships is a powerful tool for efficiently estimating pattern distributions, especially when dealing with low support thresholds that are computationally expensive to mine directly.
  • Min-Hash Overestimation is Systematic: The overestimation introduced by Min-Hash signatures is not random but systematic, allowing for modeling and correction through techniques like NNLS.

Key Results

  • The proposed "Lattice Counting" method, combined with power-law estimation and error correction, achieves significantly higher accuracy than existing methods like Hashed Sampling (HS) and naive approaches (IS, LCNC), especially for higher Jaccard similarity thresholds.
  • For instance, on the DBLP dataset, LC(0.04%) was found to be the closest to the true SSJoin size, outperforming HS(5%) and HS(2%) for T ≥ 0.4.
  • The runtime performance of the proposed method (LC) is competitive with or better than HS, with the additional benefit of much higher accuracy. The overhead for Lattice Counting and error correction was found to be negligible.
  • The method demonstrates good scalability with increasing dataset sizes.

Limitations and Future Work

  • Power-Law Hypothesis Verification: While the paper relies on power-law hypotheses for pattern distribution and pair-similarity relationships, formal statistical verification is noted as an open problem. The authors used log-log plots and approximate modeling, which were sufficient for their purposes.
  • Sampling for Pattern Mining: The paper suggests that exploiting sampling in frequent pattern mining could further improve the scalability of obtaining pattern distributions.
  • Formal Proofs for Lattice Counting: While the intuition behind the lattice counting and its coefficients is explained, a formal derivation of the coefficients is mentioned as being beyond the scope of the paper.
  • Generalization to Other Similarity Measures: The focus is on Jaccard similarity. Extending the approach to other similarity measures might require further investigation.

Summary updated

BibTeX
@article{lee2009power,
  author = {Hongrae Lee and Raymond T. Ng and Kyuseok Shim},
  title = {{Power-Law Based Estimation of Set Similarity Join Size}},
  journal = {PVLDB},
  year = {2009},
  doi = {10.14778/1687627.1687702},
}
Figure