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.5557137e-05
Overall Rank: 4,536 | 69.51%
DOI: 10.14778/1687627.1687702

Incoming Non-self Citations Over Time

Authors

1. Hongrae Lee (University of British Columbia)
2. Raymond T. Ng (University of British Columbia)
3. Kyuseok Shim (Seoul National University)

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
963	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012816649
1,933	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.3459285e-05
2,220	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.8146984e-05
4,688	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	6.4697463e-05
4,958	Similarity Join Size Estimation using Locality Sensitive Hashing	2011	VLDB	6.3394776e-05
5,207	String Similarity Measures and Joins with Synonyms	2013	SIGMOD	6.2272365e-05
5,549	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD	6.088104e-05

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.0005121339
60	The Merge/Purge Problem for Large Databases	1995	SIGMOD	0.000394583
168	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027163517
201	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025331535
435	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.0001832766
595	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00015798582
997	To Search or to Crawl? Towards a Query Optimizer for Text-Centric Tasks	2006	SIGMOD	0.00012633809
2,093	Selectivity Estimation For Boolean Queries	2000	PODS	9.0578876e-05
2,354	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.5896515e-05
2,967	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.8029216e-05
6,052	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.9028248e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,274	Set Similarity Joins on MapReduce: An Experimental Survey	2018	VLDB
2	11,759	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	3,350	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB
7	2,921	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
8	3,858	Is Min-Wise Hashing Optimal for Summarizing Set Intersection?	2014	PODS
9	3,596	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD
10	4,958	Similarity Join Size Estimation using Locality Sensitive Hashing	2011	VLDB