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: 9056
Venue: VLDB
Year: 2002
Pagerank: 6.7061802e-05
Overall Rank: 4,438 | 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
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
2,899	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.97814e-05
3,180	Approximate XML Query Answers	2004	SIGMOD	7.6599179e-05
3,209	An Efficient and Versatile Query Engine for TopX Search	2005	VLDB	7.6357297e-05
4,035	Selectivity Estimation for Fuzzy String Predicates in Large Data Sets	2005	VLDB	6.9439151e-05
5,459	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB	6.2108888e-05
8,021	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.5055705e-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.0024089429
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
470	Query Optimization for XML	1999	VLDB	0.00017965707
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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,625	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
2	12,534	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
3	666	Efficient Algorithms for Processing XPath Queries	2002	VLDB
4	2,817	On the minimization of XPath queries	2003	VLDB
5	3,659	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS
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	2,326	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD
9	8,021	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB
10	901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB