TL;DR
This paper introduces SJPC, a novel one-pass algorithm for estimating the size of similarity joins and self-joins in streaming data. SJPC offers significantly more accurate estimates with sublinear space compared to existing methods, making it ideal for large, dynamic datasets.
What Problem Does This Paper Address?
Estimating the number of "similar" record pairs in a dataset is crucial for various data management tasks like data cleaning, query optimization, and duplicate detection. Traditional methods often require multiple passes over the data or substantial memory, which is impractical for streaming environments where data arrives continuously and cannot be fully stored. Existing one-pass algorithms struggle with multi-dimensional data (records with multiple attributes) and often yield inaccurate results. This paper tackles the challenge of accurately estimating similarity join and self-join sizes in a streaming setting for multi-dimensional data, using limited memory and a single pass.
Methods
The core of the SJPC algorithm involves a clever decomposition and estimation strategy.
- Projection and Sub-value Streams: For a record with d attributes and a similarity threshold s, SJPC considers all possible combinations of k attributes (where k ranges from s to d). It generates "sub-value streams" for each k, effectively creating streams of projected records. To avoid issues with projections from different attribute combinations joining incorrectly, each projected value is encoded with its attribute combination.
- Sketching: To handle the streaming nature and limited memory, SJPC employs sketching techniques (specifically Fast-AGMS) to estimate the self-join size of each sub-value stream. This allows for sublinear space usage.
- Decomposition and Reconstruction: The algorithm leverages mathematical relationships (Lemmas 2 and 3) to decompose the problem of estimating the s-similarity self-join size into estimating self-join sizes for projections of size s through d. It then uses these estimates and a carefully derived formula (Equation 4) to reconstruct the overall s-similarity self-join size. This approach accounts for "double-counting" that arises from overlapping projections.
- Sampling: To further reduce computational cost and memory, SJPC samples from the sub-value streams. The sampling ratio r controls the trade-off between accuracy and efficiency.
Datasets
The paper evaluates SJPC on the following real-world datasets:
- DBLP5: Records from DBLP with 5 fields (title, author, journal, volume, year).
- DBLP6: Records from DBLP with 6 fields (title, author, journal, month, year, volume).
- DBLPtitles: Paper titles from DBLP, where each title is fingerprinted into 6 super-shingles, effectively creating 6 attributes.
- YFCC: A subset of the Flickr 100 million photo dataset, using 5 fields (userid, date taken, capturing device, latitude, longitude).
Additionally, synthetic datasets were generated to test scalability under varying conditions:
- Near-uniform 40-60: Randomly generated records with 40% unique and 60% having one 4-similar pair.
- Skewed 20-80: Randomly generated records with 20% unique and 80% having 15 4-similar pairs.
- Skewed 10-90: Randomly generated records with 10% unique and 90% having many 4-similar pairs.
Key Insights and Ideas
- Decomposing Similarity Joins: The core insight is that estimating multi-dimensional similarity joins can be broken down into estimating self-joins on lower-dimensional projections. This decomposition, combined with mathematical relationships between these projections, is key to an accurate estimate.
- Sketching for Streaming: Applying sketching techniques to estimate self-joins on projected streams is a powerful way to achieve sublinear space complexity in a streaming setting.
- Handling Double-Counting: The paper provides a rigorous mathematical framework (Lemmas 2 and 3) to precisely account for the overcounting that occurs when combining estimates from different projections. This is a significant improvement over heuristic approaches.
- Trade-off Management: SJPC offers tunable parameters (sampling ratio, sketch width/depth) that allow users to balance accuracy, space, and processing time based on their specific needs.
Key Results
- High Accuracy: SJPC consistently outperforms baseline methods like LSH-based bucketing and random sampling, often by an order of magnitude in terms of relative error, especially for larger similarity thresholds.
- Scalability: The algorithm scales linearly with the input size (n), making it suitable for massive datasets. Running time increases with dimensionality (d) and the gap between d and s, but remains manageable for practical scenarios.
- Sublinear Space: SJPC achieves sublinear space complexity, making it feasible for streaming environments where memory is limited.
- Offline Viability: Even in an "offline" scenario (where intermediate results can be materialized), SJPC-offline demonstrates competitive accuracy with significantly better error bounds than some multi-pass algorithms.
Limitations and Future Work
- Dimensionality: The paper acknowledges that SJPC's performance degrades with very high dimensionality. While it scales linearly with input size, the complexity grows with d.
- Future Work: The authors suggest extending the work to higher dimensions by decomposing tables into smaller attribute groupings and merging results. They also propose investigating simplifying assumptions to derive tighter bounds and exploring how similarity join size estimation can be integrated into similarity join algorithms themselves.
Summary updated