Database Paper Browser

Back to papers

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
3363
Venue
SIGMOD
Year
2002
Pagerank
9.0419716e-05
Overall Rank
2,316 | 83.89%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank Citing Paper Year Venue Pagerank
325 The History of Histograms (abridged) 2003 VLDB 0.00027378328
993 D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data 2003 SIGMOD 0.00014765816
1,198 Crossing the Structure Chasm 2003 CIDR 0.00013366708
2,010 StatiX: Making XML Count 2002 SIGMOD 9.7970026e-05
3,113 Structure and Value Synopses for XML Data Graphs 2002 VLDB 7.5469926e-05
3,419 Approximate XML Query Answers 2004 SIGMOD 7.1173416e-05
3,466 Updates for Structure Indexes 2002 VLDB 7.0695018e-05
3,511 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.0254052e-05
5,632 Bloom Histogram: Path Selectivity Estimation for XML Data with Updates 2004 VLDB 5.4014372e-05
5,663 Incremental Maintenance of XML Structural Indexes 2004 SIGMOD 5.3832923e-05
7,742 CXHist : An On-line Classification-Based Histogram for XML String Selectivity Estimation 2005 VLDB 4.6628263e-05
7,801 Realtime Analysis of Information Diffusion in Social Media 2013 VLDB 4.6469803e-05
7,827 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 4.6411831e-05
Previous Page 1 / 1 Next

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
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041786333
273 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00029390945
501 Query Optimization for XML 1999 VLDB 0.00021530411
1,046 Estimating the Selectivity of XML Path Expressions for Internet Scale Applications 2001 VLDB 0.00014462307
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
5,632 Bloom Histogram: Path Selectivity Estimation for XML Data with Updates 2004 VLDB 5.4014372e-05
7,742 CXHist : An On-line Classification-Based Histogram for XML String Selectivity Estimation 2005 VLDB 4.6628263e-05
2,507 Path Queries on Compressed XML 2003 VLDB 8.6311009e-05
12,340 Efficient Rewriting of XPath Queries Using Query Set Specifications 2009 VLDB 4.1945683e-05
3,084 On the minimization of Xpath queries 2003 VLDB 7.6011919e-05
2,855 Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach 2003 VLDB 8.0059865e-05
4,660 XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation 2002 VLDB 6.014625e-05
3,419 Approximate XML Query Answers 2004 SIGMOD 7.1173416e-05
1,046 Estimating the Selectivity of XML Path Expressions for Internet Scale Applications 2001 VLDB 0.00014462307
3,113 Structure and Value Synopses for XML Data Graphs 2002 VLDB 7.5469926e-05