Database Paper Browser

Back to papers

Selectivity Estimation For Boolean Queries

Summary: Proposes compact Monte Carlo set-hash signatures that represent the set of strings containing each substring, enabling on-the-fly estimation of correlations among substring predicates to answer arbitrary Boolean substring queries. Space-efficient, approximate method scales to super-exponential predicate combinations and empirically outperforms independence-based selectivity estimates for IR/query-optimization and query-refinement tasks. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1212
Venue
PODS
Year
2000
Pagerank
9.3807165e-05
Overall Rank
2,171 | 84.90%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank Citing Paper Year Venue Pagerank
250 Efficient set joins on similarity predicates 2004 SIGMOD 0.00030661988
475 Mining Database Structure; Or, How to Build a Data Quality Browser 2002 SIGMOD 0.00022303253
1,046 Estimating the Selectivity of XML Path Expressions for Internet Scale Applications 2001 VLDB 0.00014462307
1,686 Fast Computation of Database Operations using Graphics Processors 2004 SIGMOD 0.00010917794
3,102 Processing Set Expressions over Continuous Update Streams 2003 SIGMOD 7.5586568e-05
4,359 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 6.2569955e-05
4,438 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.1898903e-05
4,873 Power-Law Based Estimation of Set Similarity Join Size 2009 VLDB 5.8602304e-05
7,474 Cardinality Estimation of Approximate Substring Queries using Deep Learning 2022 VLDB 4.7194345e-05
7,522 Efficient and Tunable Similar Set Retrieval 2001 SIGMOD 4.7180617e-05
7,645 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 4.6896215e-05
7,708 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6721808e-05
7,742 CXHist : An On-line Classification-Based Histogram for XML String Selectivity Estimation 2005 VLDB 4.6628263e-05
9,726 Cardinality Estimation of LIKE Predicate Queries using Deep Learning 2025 SIGMOD 4.2943379e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00027358981
1,146 Estimating Alphanumeric Selectivity in the Presence of Wildcards 1996 SIGMOD 0.00013679782
1,379 Substring Selectivity Estimation 1999 PODS 0.00012286879
3,035 Multi-Dimensional Substring Selectivity Estimation 1999 VLDB 7.6748073e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,708 Is Min-Wise Hashing Optimal for Summarizing Set Intersection? 2014 PODS 6.8247903e-05
372 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00025354779
9,691 Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes 2023 SIGMOD 4.3035354e-05
1,146 Estimating Alphanumeric Selectivity in the Presence of Wildcards 1996 SIGMOD 0.00013679782
4,438 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.1898903e-05
1,981 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 9.8687545e-05
5,813 Space-efficient Substring Occurrence Estimation 2011 PODS 5.3170565e-05
3,035 Multi-Dimensional Substring Selectivity Estimation 1999 VLDB 7.6748073e-05
1,379 Substring Selectivity Estimation 1999 PODS 0.00012286879
2,779 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.1320575e-05