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.5896515e-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
784 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.00014012614
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
3,512 Efficient Approximate Entity Extraction with Edit Distance Constraints 2009 SIGMOD 7.2439455e-05
4,536 Power-Law Based Estimation of Set Similarity Join Size 2009 VLDB 6.5557137e-05
4,958 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 6.3394776e-05
5,549 Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction 2011 SIGMOD 6.088104e-05
5,657 PGMJoins: Random Join Sampling with Graphical Models 2021 SIGMOD 6.0488437e-05
5,795 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.9926463e-05
5,831 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB 5.9782109e-05
6,118 Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments 2009 VLDB 5.8813101e-05
7,561 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 5.4958573e-05
9,251 Leveraging Similarity Joins for Signal Reconstruction 2018 VLDB 5.2056825e-05
9,741 LES3: Learning-based Exact Set Similarity Search 2021 VLDB 5.1349531e-05
9,976 Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes 2023 SIGMOD 5.1031384e-05
11,257 ACE: A Cardinality Estimator for Set-Valued Queries 2025 VLDB 4.9793485e-05
12,033 Tanium Reveal: A Federated Search Engine for Querying Unstructured File Data on Large Enterprise Networks 2021 VLDB 4.9793485e-05
12,653 Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information 2011 PODS 4.9793485e-05
13,803 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.00047731453
108 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.0003305531
168 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027163517
201 Efficient set joins on similarity predicates 2004 SIGMOD 0.00025331535
295 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00021914399
707 On Synopses for Distinct-Value Estimation Under Multiset Operations 2007 SIGMOD 0.00014640173
1,826 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.5575424e-05
2,967 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB 7.8029216e-05
3,403 Benchmarking Declarative Approximate Selection Predicates 2007 SIGMOD 7.3300953e-05
3,871 A Bi-Level Bernoulli Scheme for Database Sampling 2004 SIGMOD 6.9543581e-05
4,117 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.7958711e-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,700 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB
3 1,077 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD
4 8,739 Modeling High-Dimensional Index Structures using Sampling 2001 SIGMOD
5 3,230 Similarity Query Processing for High-Dimensional Data 2020 VLDB
6 9,632 Small Selectivities Matter: Lifting the Burden of Empty Samples 2021 SIGMOD
7 4,958 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB
8 1,542 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB
9 8,110 Efficient and Tunable Similar Set Retrieval 2001 SIGMOD
10 2,093 Selectivity Estimation For Boolean Queries 2000 PODS