Structure and Value Synopses for XML Data Graphs

Summary: Augments structural XSKETCH synopses with localized stability and value-distribution summaries to model correlations between XML paths and predicates. Provides selectivity estimation and a greedy space-constrained construction heuristic for complex path expressions. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h590c86a6c3cfc4ae
Venue: VLDB
Year: 2002
Pagerank: 7.530952e-05
Overall Rank: 3,195 | 78.59%
DOI: 10.1016/B978-155860869-6/50048-2

Incoming Non-self Citations Over Time

Authors

1. Neoklis Polyzotis (University of Wisconsin)
2. Minos Garofalakis (Bell Labs, Lucent Technologies)

BibTeX Citation

@article{polyzotis_vldb02,
        title = {{Structure and Value Synopses for XML Data Graphs}},
        author = {Polyzotis, Neoklis and Garofalakis, Minos},
        journal = {PVLDB},
        series = {{VLDB} '02},
        doi = {10.1016/B978-155860869-6/50048-2},
        url = {https://doi.org/10.1016/B978-155860869-6/50048-2},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
254	The History of Histograms (abridged)	2003	VLDB	0.00022999992
1,027	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00012391703
3,263	Approximate XML Query Answers	2004	SIGMOD	7.4679565e-05
3,463	Locating Data Sources in Large Distributed Systems	2003	VLDB	7.2616713e-05
3,900	Mixed Mode XML Query Processing	2003	VLDB	6.9197487e-05
5,591	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB	6.0553413e-05
7,655	Hash-based Subgraph Query Processing Method for Graph-structured XML Documents	2008	VLDB	5.4578901e-05
8,186	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.3653848e-05
8,771	Complex Queries over Web Repositories	2003	VLDB	5.2685955e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
50	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00042977538
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033847446
131	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.000302173
222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024136952
483	Query Optimization for XML	1999	VLDB	0.00017537362
701	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.0001464136
919	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013042589
1,969	StatiX: Making XML Count	2002	SIGMOD	9.2805411e-05
2,378	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD	8.5315761e-05

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,894	Relational-Style XML Query	2008	SIGMOD
3	2,533	Path Queries on Compressed XML	2003	VLDB
4	2,897	On the minimization of XPath queries	2003	VLDB
5	919	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB
6	12,873	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
7	8,261	Semantic Query Optimization for XQuery over XML Streams	2005	VLDB
8	3,252	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB
9	3,263	Approximate XML Query Answers	2004	SIGMOD
10	2,378	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD