Substring Selectivity Estimation

Summary: Introduces MO (Maximal Overlap), a substring selectivity estimator using pruned count-suffix trees that leverages all maximal query substrings to produce better estimates. Proves MO dominates KVI under short‑memory strings and gives MOC/MOLC algs trading accuracy vs cost. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hb79e420343e6df4a
Venue: PODS
Year: 1999
Pagerank: 0.00010583833
Overall Rank: 1,461 | 90.18%
DOI: 10.1145/303976.304001

Incoming Non-self Citations Over Time

Authors

1. H. V. Jagadish (University of Illinois Urbana-Champaign)
2. Raymond T. Ng (University of British Columbia)
3. Divesh Srivastava (AT&T)

BibTeX Citation

@inproceedings{jagadish_pods99,
        address = {New York, NY, USA},
        series = {{PODS} '99},
        title = {{Substring Selectivity Estimation}},
        url = {https://dl.acm.org/doi/10.1145/303976.304001},
        doi = {10.1145/303976.304001},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Jagadish, H. V. and Ng, Raymond T. and Srivastava, Divesh},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
919	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013083677
1,061	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012213729
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011777105
2,093	Selectivity Estimation For Boolean Queries	2000	PODS	9.0578876e-05
2,144	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	8.9608583e-05
2,214	Effective Phrase Prediction	2007	VLDB	8.8195986e-05
2,967	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.8029216e-05
3,562	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.2046519e-05
4,528	XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation	2002	VLDB	6.5602044e-05
6,884	LPLM: A Neural Language Model for Cardinality Estimation of LIKE-Queries	2024	SIGMOD	5.6563432e-05
6,952	Space-efficient Substring Occurrence Estimation	2011	PODS	5.635646e-05
7,417	Cardinality Estimation of Approximate Substring Queries using Deep Learning	2022	VLDB	5.5327978e-05
8,167	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.3848674e-05
8,959	Dynamic Data Structures for Document Collections and Graphs	2015	PODS	5.2503805e-05
10,027	Cardinality Estimation of LIKE Predicate Queries using Deep Learning	2025	SIGMOD	5.0925739e-05
10,322	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD	5.0346745e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023947656
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
60	The Merge/Purge Problem for Large Databases	1995	SIGMOD	0.000394583
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.0003137356
275	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022413521
283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022214789
806	Universality of Serial Histograms	1993	VLDB	0.00013792174
1,011	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00012529816
1,163	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.00011750813

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,294	Approximate Substring Matching over Uncertain Strings	2011	VLDB
2	4,117	Selectivity Estimation for Fuzzy String Predicates in Large Data Sets	2005	VLDB
3	7,842	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
4	10,322	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD
5	919	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB
6	6,952	Space-efficient Substring Occurrence Estimation	2011	PODS
7	1,163	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD
8	2,967	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB
9	2,093	Selectivity Estimation For Boolean Queries	2000	PODS
10	3,269	Multi-Dimensional Substring Selectivity Estimation	1999	VLDB