Multi-Dimensional Substring Selectivity Estimation

Summary: Multi-dimensional count-suffix trees for substring selectivity in cross-attribute queries. A probabilistic, space-efficient construction builds pruned trees directly; estimators GNO and MO, with MO leveraging all maximal multi-dimensional substrings to capture inter-dimension correlations and outperforming GNO empirically. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8774
Venue: VLDB
Year: 1999
Pagerank: 7.6364508e-05
Overall Rank: 3,207 | 78.00%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. H. V. Jagadish (University of Michigan)
2. Olga Kapitskaia (AT&T)
3. Raymond T. Ng (University of British Columbia)
4. Divesh Srivastava (AT&T)

BibTeX Citation

@article{jagadish_vldb99,
        title = {{Multi-Dimensional Substring Selectivity Estimation}},
        author = {Jagadish, H. V. and Kapitskaia, Olga and Ng, Raymond T. and Srivastava, Divesh},
        journal = {PVLDB},
        series = {{VLDB} '99},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013334162
1,170	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011827259
2,061	Selectivity Estimation For Boolean Queries	2000	PODS	9.2445049e-05
2,648	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD	8.2957097e-05
4,035	Selectivity Estimation for Fuzzy String Predicates in Large Data Sets	2005	VLDB	6.9439151e-05
8,021	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.5055705e-05
12,841	Searching on the Secondary Structure of Protein Sequences	2002	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,097	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD
2	6,818	Space-efficient Substring Occurrence Estimation	2011	PODS
3	1,053	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD
4	901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB
5	6,491	Two-dimensional Substring Indexing	2001	PODS
6	1,140	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD
7	2,648	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD
8	2,899	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB
9	2,061	Selectivity Estimation For Boolean Queries	2000	PODS
10	1,427	Substring Selectivity Estimation	1999	PODS