Similarity Join Size Estimation using Locality Sensitive Hashing
Summary: Introduces LSH-SS, a sampling-based VSJ estimator leveraging Locality-Sensitive Hashing to enable accurate sampling at high similarity thresholds, generalizing SSJ to vector representations (e.g., TF-IDF). Empirical results show LSH-SS delivers higher accuracy and lower variance than random sampling and an adapted SSJ baseline across thresholds on real datasets. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Hongrae Lee
- 2. Raymond T. Ng
- 3. Kyuseok Shim
Incoming Citations (Sorted by Pagerank)
Showing 5 of 5 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,396 | Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search | 2012 | SIGMOD | 0.00012215253 |
| 2,729 | String Similarity Joins: An Experimental Evaluation | 2014 | VLDB | 8.2175463e-05 |
| 2,971 | Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models | 2017 | VLDB | 7.7935535e-05 |
| 5,152 | String Similarity Measures and Joins with Synonyms | 2013 | SIGMOD | 5.6550754e-05 |
| 5,477 | Learned Cardinality Estimation for Similarity Queries | 2021 | SIGMOD | 5.4856699e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 10 of 10 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 18 | On Random Sampling over Joins | 1999 | SIGMOD | 0.00092569117 |
| 92 | Practical Selectivity Estimation through Adaptive Sampling | 1990 | SIGMOD | 0.00051431888 |
| 100 | On the Propagation of Errors in the Size of Join Results | 1991 | SIGMOD | 0.00050033475 |
| 248 | Efficient set joins on similarity predicates | 2004 | SIGMOD | 0.00030888982 |
| 264 | Efficient Exact Set-Similarity Joins | 2006 | VLDB | 0.00029950264 |
| 550 | Tracking Join and Self-Join Sizes in Limited Storage | 1999 | PODS | 0.00020346247 |
| 553 | Bifocal Sampling for Skew-Resistant Join Size Estimation | 1996 | SIGMOD | 0.00020272747 |
| 1,254 | Fixed-Precision Estimation of Join Selectivity | 1993 | PODS | 0.00013018797 |
| 2,779 | Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries | 2008 | VLDB | 8.1314377e-05 |
| 4,871 | Power-Law Based Estimation of Set Similarity Join Size | 2009 | VLDB | 5.8568724e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,350 | Overlap Set Similarity Joins with Theoretical Guarantees | 2018 | SIGMOD | 6.2576191e-05 |
| 3,461 | Leveraging Set Relations in Exact Set Similarity Join | 2017 | VLDB | 7.0696567e-05 |
| 6,240 | Scaling Similarity Joins over Tree-Structured Data | 2015 | VLDB | 5.1362097e-05 |
| 8,759 | Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search | 2015 | PODS | 4.4520434e-05 |
| 579 | Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting | 2012 | SIGMOD | 0.0001982328 |
| 4,808 | On the Complexity of Inner Product Similarity Join | 2016 | PODS | 5.9040739e-05 |
| 248 | Efficient set joins on similarity predicates | 2004 | SIGMOD | 0.00030888982 |
| 2,779 | Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries | 2008 | VLDB | 8.1314377e-05 |
| 4,871 | Power-Law Based Estimation of Set Similarity Join Size | 2009 | VLDB | 5.8568724e-05 |
| 8,899 | Fast Approximate Similarity Join in Vector Databases | 2025 | SIGMOD | 4.4229886e-05 |