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.5577589e-05
Overall Rank: 3,184 | 78.60%
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
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
1,023	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00012432693
3,246	Approximate XML Query Answers	2004	SIGMOD	7.4946879e-05
3,454	Locating Data Sources in Large Distributed Systems	2003	VLDB	7.2892132e-05
3,889	Mixed Mode XML Query Processing	2003	VLDB	6.9447533e-05
5,580	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB	6.0769576e-05
7,635	Hash-based Subgraph Query Processing Method for Graph-structured XML Documents	2008	VLDB	5.4785904e-05
8,167	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.3848674e-05
8,754	Complex Queries over Web Repositories	2003	VLDB	5.2846592e-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.00043130126
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
130	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030320165
222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024218831
482	Query Optimization for XML	1999	VLDB	0.00017598607
701	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.00014680907
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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,680	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
2	12,845	Relational-Style XML Query	2008	SIGMOD
3	2,525	Path Queries on Compressed XML	2003	VLDB
4	2,881	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,824	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
7	8,237	Semantic Query Optimization for XQuery over XML Streams	2005	VLDB
8	3,233	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB
9	3,246	Approximate XML Query Answers	2004	SIGMOD
10	2,368	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD