CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation

Summary: CXHist estimates XML path–string selectivities by modeling high-cardinality leaf values, rather than only tag paths. It incrementally learns feedback-based buckets and feature distributions as a Bayesian classifier, supporting exact- and substring-match queries. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9444
Venue: VLDB
Year: 2005
Pagerank: 5.5055705e-05
Overall Rank: 8,021 | 44.97%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Lipyeow Lim (International Business Machines T. J. Watson Research Center)
2. Min Wang (International Business Machines T. J. Watson Research Center)
3. Jeffrey Scott Vitter (Purdue University)

BibTeX Citation

@article{lim_vldb05,
        title = {{CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation}},
        author = {Lim, Lipyeow and Wang, Min and Vitter, Jeffrey Scott},
        journal = {PVLDB},
        series = {{VLDB} '05},
        pages = {1187--1198},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,157	A Black-Box Approach to Query Cardinality Estimation	2007	CIDR	9.0625592e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
362	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD	0.00020125068
365	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00020041735
448	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00018292618
901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013334162
1,140	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.0001200574
1,427	Substring Selectivity Estimation	1999	PODS	0.00010812749
1,744	System RX: One Part Relational, One Part XML	2005	SIGMOD	9.868841e-05
1,900	StatiX: Making XML Count	2002	SIGMOD	9.5168326e-05
2,061	Selectivity Estimation For Boolean Queries	2000	PODS	9.2445049e-05
2,326	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD	8.748172e-05
3,129	Structure and Value Synopses for XML Data Graphs	2002	VLDB	7.7256156e-05
3,207	Multi-Dimensional Substring Selectivity Estimation	1999	VLDB	7.6364508e-05
4,438	XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation	2002	VLDB	6.7061802e-05
5,459	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB	6.2108888e-05
9,453	VXMLR: A Visual XML-Relational Database System	2001	VLDB	5.265685e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,476	XPath Whole Query Optimization	2010	VLDB
2	934	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB
3	2,625	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
4	168	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD
5	3,180	Approximate XML Query Answers	2004	SIGMOD
6	3,129	Structure and Value Synopses for XML Data Graphs	2002	VLDB
7	5,459	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB
8	901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB
9	2,326	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD
10	4,438	XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation	2002	VLDB