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.3877451e-05
Overall Rank
2,168 | 84.94%
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
248 Efficient set joins on similarity predicates 2004 SIGMOD 0.00030888982
481 Mining Database Structure; Or, How to Build a Data Quality Browser 2002 SIGMOD 0.000221538
1,045 Estimating the Selectivity of XML Path Expressions for Internet Scale Applications 2001 VLDB 0.00014451072
1,685 Fast Computation of Database Operations using Graphics Processors 2004 SIGMOD 0.0001090924
3,108 Processing Set Expressions over Continuous Update Streams 2003 SIGMOD 7.5547127e-05
4,352 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 6.2542257e-05
4,433 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.1852739e-05
4,871 Power-Law Based Estimation of Set Similarity Join Size 2009 VLDB 5.8568724e-05
7,473 Cardinality Estimation of Approximate Substring Queries using Deep Learning 2022 VLDB 4.7149077e-05
7,521 Efficient and Tunable Similar Set Retrieval 2001 SIGMOD 4.7135369e-05
7,644 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 4.6853638e-05
7,707 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6676985e-05
7,740 CXHist : An On-line Classification-Based Histogram for XML String Selectivity Estimation 2005 VLDB 4.658789e-05
9,725 Cardinality Estimation of LIKE Predicate Queries using Deep Learning 2025 SIGMOD 4.290223e-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.0002737538
1,145 Estimating Alphanumeric Selectivity in the Presence of Wildcards 1996 SIGMOD 0.00013672625
1,379 Substring Selectivity Estimation 1999 PODS 0.00012280308
3,036 Multi-Dimensional Substring Selectivity Estimation 1999 VLDB 7.671524e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,713 Is Min-Wise Hashing Optimal for Summarizing Set Intersection? 2014 PODS 6.8182579e-05
373 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00025354685
9,690 Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes 2023 SIGMOD 4.2994116e-05
1,145 Estimating Alphanumeric Selectivity in the Presence of Wildcards 1996 SIGMOD 0.00013672625
4,433 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.1852739e-05
1,978 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 9.8764627e-05
5,825 Space-efficient Substring Occurrence Estimation 2011 PODS 5.3119504e-05
3,036 Multi-Dimensional Substring Selectivity Estimation 1999 VLDB 7.671524e-05
1,379 Substring Selectivity Estimation 1999 PODS 0.00012280308
2,779 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.1314377e-05