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: 10035
Venue: VLDB
Year: 2009
Pagerank: 6.6972929e-05
Overall Rank: 4,450 | 69.48%
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
975	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012870645
1,886	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.5358137e-05
2,186	String Similarity Joins: An Experimental Evaluation	2014	VLDB	9.0001436e-05
4,617	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	6.604437e-05
4,857	Similarity Join Size Estimation using Locality Sensitive Hashing	2011	VLDB	6.4752373e-05
5,088	String Similarity Measures and Joins with Synonyms	2013	SIGMOD	6.3673276e-05
5,412	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD	6.2272563e-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
27	Fast Algorithms for Mining Association Rules	1994	VLDB	0.00052255472
58	The Merge/Purge Problem for Large Databases	1995	SIGMOD	0.00040116748
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
200	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025597287
432	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00018572055
586	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00016124396
974	To Search or to Crawl? Towards a Query Optimizer for Text-Centric Tasks	2006	SIGMOD	0.00012870746
2,061	Selectivity Estimation For Boolean Queries	2000	PODS	9.2445049e-05
2,308	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.7738996e-05
2,899	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.97814e-05
5,932	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	6.0369275e-05

Semantically Similar Papers

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