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
9860
Venue
VLDB
Year
2008
Pagerank
8.7738996e-05
Overall Rank
2,308 | 84.17%
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.00014147905
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
3,446 Efficient Approximate Entity Extraction with Edit Distance Constraints 2009 SIGMOD 7.4087786e-05
4,450 Power-Law Based Estimation of Set Similarity Join Size 2009 VLDB 6.6972929e-05
4,857 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 6.4752373e-05
5,412 Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction 2011 SIGMOD 6.2272563e-05
5,551 PGMJoins: Random Join Sampling with Graphical Models 2021 SIGMOD 6.1782856e-05
5,667 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 6.1279762e-05
5,743 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB 6.1025457e-05
5,995 Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments 2009 VLDB 6.0155431e-05
7,433 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 5.6197531e-05
9,076 Leveraging Similarity Joins for Signal Reconstruction 2018 VLDB 5.3251649e-05
9,793 Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes 2023 SIGMOD 5.2193018e-05
10,851 ACE: A Cardinality Estimator for Set-Valued Queries 2025 VLDB 5.093636e-05
11,702 LES3: Learning-based Exact Set Similarity Search 2021 VLDB 5.093636e-05
11,730 Tanium Reveal: A Federated Search Engine for Querying Unstructured File Data on Large Enterprise Networks 2021 VLDB 5.093636e-05
12,362 Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information 2011 PODS 5.093636e-05
13,489 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
35 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00048481081
107 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00033511706
169 Efficient Exact Set-Similarity Joins 2006 VLDB 0.0002743469
200 Efficient set joins on similarity predicates 2004 SIGMOD 0.00025597287
288 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00022296371
689 On Synopses for Distinct-Value Estimation Under Multiset Operations 2007 SIGMOD 0.00014940023
1,806 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.7112151e-05
2,899 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB 7.97814e-05
3,356 Benchmarking Declarative Approximate Selection Predicates 2007 SIGMOD 7.490881e-05
3,803 A Bi-Level Bernoulli Scheme for Database Sampling 2004 SIGMOD 7.1114677e-05
4,035 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.9439151e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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