Database Paper Browser

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
9670
Venue
VLDB
Year
2008
Pagerank
8.1314377e-05
Overall Rank
2,779 | 80.69%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank Citing Paper Year Venue Pagerank
1,161 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.00013579831
1,396 Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search 2012 SIGMOD 0.00012215253
2,588 Pass-Join: A Partition-based Method for Similarity Joins 2012 VLDB 8.4872437e-05
3,583 Efficient Approximate Entity Extraction with Edit Distance Constraints 2009 SIGMOD 6.944299e-05
4,871 Power-Law Based Estimation of Set Similarity Join Size 2009 VLDB 5.8568724e-05
5,071 Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction 2011 SIGMOD 5.7122974e-05
5,222 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 5.6180462e-05
5,423 Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments 2009 VLDB 5.5143276e-05
5,892 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.2829767e-05
5,952 PGMJoins: Random Join Sampling with Graphical Models 2021 SIGMOD 5.2547498e-05
6,481 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB 5.039683e-05
7,644 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 4.6853638e-05
8,924 Leveraging Similarity Joins for Signal Reconstruction 2018 VLDB 4.4229886e-05
9,690 Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes 2023 SIGMOD 4.2994116e-05
10,598 ACE: A Cardinality Estimator for Set-Valued Queries 2025 VLDB 4.1905499e-05
11,508 LES3: Learning-based Exact Set Similarity Search 2021 VLDB 4.1905499e-05
11,537 Tanium Reveal: A Federated Search Engine for Querying Unstructured File Data on Large Enterprise Networks 2021 VLDB 4.1905499e-05
12,174 Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information 2011 PODS 4.1905499e-05
13,300 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
63 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063595699
125 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00044946098
248 Efficient set joins on similarity predicates 2004 SIGMOD 0.00030888982
264 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00029950264
380 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00024943236
737 On Synopses for Distinct-Value Estimation Under Multiset Operations 2007 SIGMOD 0.00017377393
1,790 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 0.00010529479
3,229 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB 7.3390133e-05
3,258 Benchmarking Declarative Approximate Selection Predicates 2007 SIGMOD 7.3129307e-05
4,100 A Bi-Level Bernoulli Scheme for Database Sampling 2004 SIGMOD 6.4473679e-05
4,433 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.1852739e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
248 Efficient set joins on similarity predicates 2004 SIGMOD 0.00030888982
10,227 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB 4.1905499e-05
1,240 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00013090678
7,770 Modeling High-Dimensional Index Structures using Sampling 2001 SIGMOD 4.6515743e-05
4,273 Similarity Query Processing for High-Dimensional Data 2020 VLDB 6.2932217e-05
9,387 Small Selectivities Matter: Lifting the Burden of Empty Samples 2021 SIGMOD 4.341968e-05
5,222 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 5.6180462e-05
1,978 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 9.8764627e-05
7,521 Efficient and Tunable Similar Set Retrieval 2001 SIGMOD 4.7135369e-05
2,168 Selectivity Estimation For Boolean Queries 2000 PODS 9.3877451e-05