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.5366364e-05
Overall Rank: 4,545 | 69.54%
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
254	The History of Histograms (abridged)	2003	VLDB	0.00022999992
2,981	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.7739779e-05
3,263	Approximate XML Query Answers	2004	SIGMOD	7.4679565e-05
3,288	An Efficient and Versatile Query Engine for TopX Search	2005	VLDB	7.4398818e-05
4,138	Selectivity Estimation for Fuzzy String Predicates in Large Data Sets	2005	VLDB	6.7706361e-05
5,591	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB	6.0553413e-05
8,186	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.3653848e-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.0023948467
372	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019768921
457	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017915659
483	Query Optimization for XML	1999	VLDB	0.00017537362
919	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013042589
1,164	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.0001170903
1,466	Substring Selectivity Estimation	1999	PODS	0.00010546176

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,691	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
2	12,873	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
3	683	Efficient Algorithms for Processing XPath Queries	2002	VLDB
4	2,897	On the minimization of XPath queries	2003	VLDB
5	3,755	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS
6	3,195	Structure and Value Synopses for XML Data Graphs	2002	VLDB
7	5,591	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB
8	2,378	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD
9	8,186	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