Introduction
In data cleaning, record matching, and Open Data search, identifying records $X$ that "contain" a query $Q$ is a fundamental task. This is typically measured by containment similarity: the ratio of the intersection size to the query size, defined as $C(Q, X) = \frac{|Q \cap X|}{|Q|}$.
Unlike the symmetric Jaccard similarity, containment is asymmetric, making standard Locality Sensitive Hashing (LSH) techniques difficult to apply directly. Current state-of-the-art methods like LSH-E attempt to bridge this gap by transforming containment into a Jaccard similarity problem. However, this "Jaccard detour" introduces significant estimation variance and struggles with real-world data distributions where record sizes and element frequencies are highly skewed. This paper introduces GB-KMV (Global-threshold Buffer KMV), a data-aware sketching technique that estimates intersection sizes directly, achieving up to a 100x speedup over LSH-E with superior accuracy.
Notation and Preliminaries
To understand the mechanics of GB-KMV, it is essential to define the parameters governing the sketch and the similarity thresholds used in the search process.
The GB-KMV Approach
GB-KMV builds upon the $k$-minimum values (KMV) sketch but introduces two critical innovations to handle the variance inherent in containment estimation: a global threshold and a frequency buffer.
1. G-KMV (Global Threshold)
Standard KMV sketches maintain the $k$ smallest hash values for each record. However, when record sizes vary significantly, a fixed $k$ leads to inconsistent sampling rates. GB-KMV utilizes a global threshold $\tau$. By keeping all hash values below $\tau$ across the entire dataset, the sketch ensures a uniform sampling rate, which theoretically provides a more stable and accurate estimate for intersections, particularly for containment queries.
2. Frequency Buffer
Real-world datasets often follow a power-law distribution (Zipf's law), where a small number of "heavy hitter" elements appear in a large portion of the records. These frequent elements contribute disproportionately to estimation variance. GB-KMV addresses this by employing a small, exact bitmap buffer ($L_H$) to store the $r$ most frequent elements. This allows the system to handle high-frequency elements exactly, while the G-KMV sketch ($L_{GKMV}$) handles the "long tail" of infrequent elements.
3. Cost Model Optimization
The effectiveness of GB-KMV relies on balancing the space budget $b$ between the buffer size $r$ and the threshold $\tau$. The authors provide a theoretical cost model to calculate the optimal parameters based on the dataset's specific distribution, ensuring the highest possible accuracy for a given memory footprint.
Key Results and Evaluation
The authors evaluated GB-KMV against LSH-E across seven diverse datasets, including the massive WDC Web Table (262 million records).
- Efficiency: GB-KMV demonstrated remarkable speed, outperforming LSH-E by over two orders of magnitude (100x) on several benchmarks. This is largely due to avoiding the complex transformations and multiple estimations required by the Jaccard-based LSH-E.
- Accuracy: By estimating the intersection directly and isolating high-variance elements in the buffer, GB-KMV consistently achieved higher F1 scores. On the Canadian Open Data (COD) dataset, GB-KMV maintained an F1 score near 0.8, while LSH-E fell below 0.6.
- Scalability: On the 262M-record WDC dataset, GB-KMV's index construction was significantly faster and more memory-efficient than LSH-E, proving its viability for web-scale applications.
Conclusion
GB-KMV represents a shift from data-independent hashing to data-aware sketching. By exploiting the natural skewness of real-world data through global thresholds and frequency buffers, it provides a faster, more accurate, and more scalable solution for approximate containment similarity search than existing Jaccard-based transformations.
Summary updated