DBScholar

Back to papers

Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries

Summary: Hashed Samples designs selectivity estimators for weighted set similarity queries (TF-IDF/BM25) using a priori constructed samples. It avoids uniform sampling pitfalls, proves accuracy theoretically, and delivers orders-of-magnitude speedups with small space overhead compared with exact solutions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h75c8040cd0bc21e5
Venue
VLDB
Year
2008
Pagerank
8.5872598e-05
Overall Rank
2,354 | 84.18%
DOI
10.14778/1453856.1453883

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{hadjieleftheriou_vldb08,
        title = {{Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries}},
        author = {Hadjieleftheriou, Marios and Yu, Xiaohui and Koudas, Nick and Srivastava, Divesh},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {1},
        number = {1},
        pages = {201--212},
        doi = {10.14778/1453856.1453883},
        url = {https://doi.org/10.14778/1453856.1453883},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank Citing Paper Year Venue Pagerank
772 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.0001409096
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
3,512 Efficient Approximate Entity Extraction with Edit Distance Constraints 2009 SIGMOD 7.2405277e-05
4,538 Power-Law Based Estimation of Set Similarity Join Size 2009 VLDB 6.5526273e-05
4,960 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 6.3365273e-05
5,551 Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction 2011 SIGMOD 6.0852227e-05
5,657 PGMJoins: Random Join Sampling with Graphical Models 2021 SIGMOD 6.0461e-05
5,797 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.9898117e-05
5,829 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB 5.9764044e-05
6,119 Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments 2009 VLDB 5.8785289e-05
7,567 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 5.4933119e-05
9,261 Leveraging Similarity Joins for Signal Reconstruction 2018 VLDB 5.2032182e-05
9,746 LES3: Learning-based Exact Set Similarity Search 2021 VLDB 5.1325223e-05
9,983 Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes 2023 SIGMOD 5.1007226e-05
11,265 ACE: A Cardinality Estimator for Set-Valued Queries 2025 VLDB 4.9769913e-05
12,039 Tanium Reveal: A Federated Search Engine for Querying Unstructured File Data on Large Enterprise Networks 2021 VLDB 4.9769913e-05
12,659 Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information 2011 PODS 4.9769913e-05
13,808 Orca-SR: A Real-Time Traffic Engineering Framework leveraging Similarity Joins 2020 VLDB -
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
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.0004772731
108 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00033040246
168 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027151132
201 Efficient set joins on similarity predicates 2004 SIGMOD 0.00025319937
295 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00021908194
707 On Synopses for Distinct-Value Estimation Under Multiset Operations 2007 SIGMOD 0.00014633741
1,826 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.5535288e-05
2,969 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB 7.7993378e-05
3,403 Benchmarking Declarative Approximate Selection Predicates 2007 SIGMOD 7.3266624e-05
3,872 A Bi-Level Bernoulli Scheme for Database Sampling 2004 SIGMOD 6.9512121e-05
4,118 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.7927394e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 201 Efficient set joins on similarity predicates 2004 SIGMOD
2 10,710 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB
3 1,078 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD
4 8,747 Modeling High-Dimensional Index Structures using Sampling 2001 SIGMOD
5 9,640 Small Selectivities Matter: Lifting the Burden of Empty Samples 2021 SIGMOD
6 3,232 Similarity Query Processing for High-Dimensional Data 2020 VLDB
7 4,960 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB
8 1,543 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB
9 8,117 Efficient and Tunable Similar Set Retrieval 2001 SIGMOD
10 2,094 Selectivity Estimation For Boolean Queries 2000 PODS