Approximate XML Query Answers

Summary: Proposes TREESKETCH synopses for compact, approximate XML query answering over large tree-structured data. Introduces novel construction algorithms and an error metric, enabling fast twig queries with high accuracy and outperforming selectivity-only approaches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h52e77ae8cbbc4b7b
Venue: SIGMOD
Year: 2004
Pagerank: 7.4946879e-05
Overall Rank: 3,246 | 78.18%
DOI: 10.1145/1007568.1007599

Incoming Non-self Citations Over Time

Authors

1. Neoklis Polyzotis (University of California Santa Cruz)
2. Minos Garofalakis (AT&T)
3. Yannis Ioannidis (University of Athens)

BibTeX Citation

@inproceedings{polyzotis_sigmod04,
        title = {{Approximate XML Query Answers}},
        author = {Polyzotis, Neoklis and Garofalakis, Minos and Ioannidis, Yannis},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007599},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007599},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,625	Statistical Learning Techniques for Costing XML Queries	2005	VLDB	8.2089383e-05
2,974	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.7938744e-05
3,851	Graph-Based Synopses for Relational Selectivity Estimation	2006	SIGMOD	6.9785886e-05
4,663	Approximate Matching of Hierarchical Data Using pq-Grams	2005	VLDB	6.4810192e-05
4,979	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	6.3300966e-05
5,635	Structure and Content Scoring for XML	2005	VLDB	6.0575292e-05
6,691	Query Relaxation Using Malleable Schemas	2007	SIGMOD	5.70723e-05
6,800	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.6792071e-05
7,699	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB	5.4751052e-05
8,561	Materialized View Selection for XQuery Workloads	2012	SIGMOD	5.314012e-05
12,989	AQAX: A System for Approximate XML Query Answers	2006	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
32	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00049737458
309	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021384073
448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00018129161
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,960	StatiX: Making XML Count	2002	SIGMOD	9.3125715e-05
2,368	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD	8.5622073e-05
2,525	Path Queries on Compressed XML	2003	VLDB	8.343313e-05
3,184	Structure and Value Synopses for XML Data Graphs	2002	VLDB	7.5577589e-05
3,233	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB	7.5033766e-05
4,528	XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation	2002	VLDB	6.5602044e-05
8,325	Containment Join Size Estimation: Models and Methods	2003	SIGMOD	5.3540828e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,889	Mixed Mode XML Query Processing	2003	VLDB
2	7,057	Query Efficiency in Probabilistic XML Models	2008	SIGMOD
3	2,747	Approximate XML Joins	2002	SIGMOD
4	12,701	Certain Answers for XML Queries	2010	PODS
5	1,599	Conjunctive Queries over Trees	2004	PODS
6	2,680	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
7	919	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB
8	12,989	AQAX: A System for Approximate XML Query Answers	2006	VLDB
9	3,184	Structure and Value Synopses for XML Data Graphs	2002	VLDB
10	2,368	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD