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: 1211
Venue: PODS
Year: 2000
Pagerank: 9.2445049e-05
Overall Rank: 2,061 | 85.87%
DOI: 10.1145/335168.335225

Incoming Non-self Citations Over Time

Authors

1. Zhiyuan Chen (Cornell University)
2. Flip Korn (AT&T)
3. Nick Koudas (AT&T)
4. S. Muthukrishnan (AT&T)

BibTeX Citation

@inproceedings{chen_pods00,
        address = {New York, NY, USA},
        series = {{PODS} '00},
        title = {{Selectivity Estimation For Boolean Queries}},
        url = {https://dl.acm.org/doi/10.1145/335168.335225},
        doi = {10.1145/335168.335225},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chen, Zhiyuan and Korn, Flip and Koudas, Nick and Muthukrishnan, S.},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
200	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025597287
432	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00018572055
901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013334162
1,452	Fast Computation of Database Operations using Graphics Processors	2004	SIGMOD	0.00010745803
3,197	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.6439415e-05
3,545	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.3249967e-05
4,035	Selectivity Estimation for Fuzzy String Predicates in Large Data Sets	2005	VLDB	6.9439151e-05
4,450	Power-Law Based Estimation of Set Similarity Join Size	2009	VLDB	6.6972929e-05
7,268	Cardinality Estimation of Approximate Substring Queries using Deep Learning	2022	VLDB	5.6597123e-05
7,433	Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations	2015	VLDB	5.6197531e-05
7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD	5.5664611e-05
7,942	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD	5.5181056e-05
8,021	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.5055705e-05
9,844	Cardinality Estimation of LIKE Predicate Queries using Deep Learning	2025	SIGMOD	5.2094602e-05

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
267	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022798161
1,140	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.0001200574
1,427	Substring Selectivity Estimation	1999	PODS	0.00010812749
3,207	Multi-Dimensional Substring Selectivity Estimation	1999	VLDB	7.6364508e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,795	Is Min-Wise Hashing Optimal for Summarizing Set Intersection?	2014	PODS
2	280	Selectivity Estimation using Probabilistic Models	2001	SIGMOD
3	9,793	Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes	2023	SIGMOD
4	1,140	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD
5	4,035	Selectivity Estimation for Fuzzy String Predicates in Large Data Sets	2005	VLDB
6	1,536	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB
7	6,818	Space-efficient Substring Occurrence Estimation	2011	PODS
8	3,207	Multi-Dimensional Substring Selectivity Estimation	1999	VLDB
9	1,427	Substring Selectivity Estimation	1999	PODS
10	2,308	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB