XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation

Summary: XPathLearner: an on-line, self-tuning Markov histogram for XML path selectivity without full data scans. Uses query feedback to refine workload-aware statistics under memory constraints and adapts to data changes, enabling accurate planning for Internet-scale XML repos. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h2330302343d90675
Venue: VLDB
Year: 2002
Pagerank: 6.5602044e-05
Overall Rank: 4,528 | 69.56%
DOI: 10.1016/B978-155860869-6/50046-9

Incoming Non-self Citations Over Time

Authors

1. Lipyeow Lim (Duke University)
2. Min Wang (IBM)
3. Sriram Padmanabhan (IBM)
4. Jeffrey Scott Vitter (Duke University)
5. Ronald Parr (Duke University)

BibTeX Citation

@article{lim_vldb02,
        title = {{XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation}},
        author = {Lim, Lipyeow and Wang, Min and Padmanabhan, Sriram and Vitter, Jeffrey Scott and Parr, Ronald},
        journal = {PVLDB},
        series = {{VLDB} '02},
        doi = {10.1016/B978-155860869-6/50046-9},
        url = {https://doi.org/10.1016/B978-155860869-6/50046-9},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
2,967	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.8029216e-05
3,246	Approximate XML Query Answers	2004	SIGMOD	7.4946879e-05
3,276	An Efficient and Versatile Query Engine for TopX Search	2005	VLDB	7.4678085e-05
4,117	Selectivity Estimation for Fuzzy String Predicates in Large Data Sets	2005	VLDB	6.7958711e-05
5,580	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB	6.0769576e-05
8,167	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.3848674e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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
371	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019829769
454	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017962189
482	Query Optimization for XML	1999	VLDB	0.00017598607
919	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013083677
1,163	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.00011750813
1,461	Substring Selectivity Estimation	1999	PODS	0.00010583833

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,680	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
2	12,824	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
3	679	Efficient Algorithms for Processing XPath Queries	2002	VLDB
4	2,881	On the minimization of XPath queries	2003	VLDB
5	3,746	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS
6	3,184	Structure and Value Synopses for XML Data Graphs	2002	VLDB
7	5,580	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB
8	2,368	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD
9	8,167	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB
10	919	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB