Statistical Synopses for Graph-Structured XML Databases

Summary: Proposes XSKETCH, a graph-synopsis for XML data that enables accurate selectivity estimates for complex path expressions over graph-structured XML. Proves NP-hardness of constructing an optimal synopsis and presents a greedy forward-refinement algorithm on the label-split graph, validated on synthetic and real datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3425
Venue: SIGMOD
Year: 2002
Pagerank: 8.748172e-05
Overall Rank: 2,326 | 84.05%
DOI: 10.1145/564691.564733

Incoming Non-self Citations Over Time

Authors

1. Neoklis Polyzotis (University of Wisconsin)
2. Minos Garofalakis (AT&T)

BibTeX Citation

@inproceedings{polyzotis_sigmod02,
        title = {{Statistical Synopses for Graph-Structured XML Databases}},
        author = {Polyzotis, Neoklis and Garofalakis, Minos},
        series = {{SIGMOD} '02},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/564691.564733},
        url = {https://dl.acm.org/doi/10.1145/564691.564733},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
1,008	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00012688008
1,540	Crossing the Structure Chasm	2003	CIDR	0.00010430413
1,900	StatiX: Making XML Count	2002	SIGMOD	9.5168326e-05
3,070	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.7900444e-05
3,129	Structure and Value Synopses for XML Data Graphs	2002	VLDB	7.7256156e-05
3,180	Approximate XML Query Answers	2004	SIGMOD	7.6599179e-05
3,421	Updates for Structure Indexes	2002	VLDB	7.4273213e-05
5,459	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB	6.2108888e-05
5,688	Incremental Maintenance of XML Structural Indexes	2004	SIGMOD	6.1208788e-05
8,021	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.5055705e-05
8,117	Realtime Analysis of Information Diffusion in Social Media	2013	VLDB	5.4837975e-05
8,155	Containment Join Size Estimation: Models and Methods	2003	SIGMOD	5.4766319e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
213	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024723025
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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,459	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB
2	8,021	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB
3	2,472	Path Queries on Compressed XML	2003	VLDB
4	12,534	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
5	2,817	On the minimization of XPath queries	2003	VLDB
6	2,625	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
7	4,438	XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation	2002	VLDB
8	3,180	Approximate XML Query Answers	2004	SIGMOD
9	901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB
10	3,129	Structure and Value Synopses for XML Data Graphs	2002	VLDB