DBScholar

Back to papers

Power-Law Based Estimation of Set Similarity Join Size

Summary: Power-law guided estimation of SSJoin size via compact Min-Hash signatures; exploits frequent signature patterns to count support. A novel lattice-based IE counting method yields linear complexity in lattice size, enabling light-weight mining with high accuracy and efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h70a4179d17e6d8fe
Venue
VLDB
Year
2009
Pagerank
6.5526273e-05
Overall Rank
4,538 | 69.51%
DOI
10.14778/1687627.1687702

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{lee_vldb09,
        title = {{Power-Law Based Estimation of Set Similarity Join Size}},
        author = {Lee, Hongrae and Ng, Raymond T. and Shim, Kyuseok},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687702},
        url = {https://doi.org/10.14778/1687627.1687702},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank Citing Paper Year Venue Pagerank
965 Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search 2012 SIGMOD 0.00012810695
1,934 Pass-Join: A Partition-based Method for Similarity Joins 2012 VLDB 9.341845e-05
2,223 String Similarity Joins: An Experimental Evaluation 2014 VLDB 8.8105347e-05
4,690 Learned Cardinality Estimation for Similarity Queries 2021 SIGMOD 6.4667478e-05
4,960 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 6.3365273e-05
5,210 String Similarity Measures and Joins with Synonyms 2013 SIGMOD 6.2243094e-05
5,551 Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction 2011 SIGMOD 6.0852227e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
29 Fast Algorithms for Mining Association Rules 1994 VLDB 0.00051189413
60 The Merge/Purge Problem for Large Databases 1995 SIGMOD 0.00039440583
168 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027151132
201 Efficient set joins on similarity predicates 2004 SIGMOD 0.00025319937
435 Mining Database Structure; Or, How to Build a Data Quality Browser 2002 SIGMOD 0.0001831946
595 ConQuer: Efficient Management of Inconsistent Databases 2005 SIGMOD 0.00015791577
998 To Search or to Crawl? Towards a Query Optimizer for Text-Centric Tasks 2006 SIGMOD 0.00012628727
2,094 Selectivity Estimation For Boolean Queries 2000 PODS 9.0536495e-05
2,354 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.5872598e-05
2,969 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB 7.7993378e-05
6,054 Spatial Join Selectivity Using Power Laws 2000 SIGMOD 5.9000316e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,275 Set Similarity Joins on MapReduce: An Experimental Survey 2018 VLDB
2 11,765 A Two-Level Signature Scheme for Stable Set Similarity Joins 2023 VLDB
3 2,513 An Empirical Evaluation of Set Similarity Join Techniques 2016 VLDB
4 201 Efficient set joins on similarity predicates 2004 SIGMOD
5 168 Efficient Exact Set-Similarity Joins 2006 VLDB
6 2,923 Leveraging Set Relations in Exact Set Similarity Join 2017 VLDB
7 3,350 An Efficient Partition Based Method for Exact Set Similarity Joins 2016 VLDB
8 3,859 Is Min-Wise Hashing Optimal for Summarizing Set Intersection? 2014 PODS
9 3,598 Overlap Set Similarity Joins with Theoretical Guarantees 2018 SIGMOD
10 4,960 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB