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: 9058
Venue: VLDB
Year: 2002
Pagerank: 7.7256156e-05
Overall Rank: 3,129 | 78.54%
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
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
3,180	Approximate XML Query Answers	2004	SIGMOD	7.6599179e-05
3,382	Locating Data Sources in Large Distributed Systems	2003	VLDB	7.4565087e-05
3,814	Mixed Mode XML Query Processing	2003	VLDB	7.1026815e-05
5,459	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB	6.2108888e-05
7,494	Hash-based Subgraph Query Processing Method for Graph-structured XML Documents	2008	VLDB	5.6043267e-05
8,021	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.5055705e-05
8,618	Complex Queries over Web Repositories	2003	VLDB	5.4001665e-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
48	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00044033592
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
124	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030950263
213	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024723025
470	Query Optimization for XML	1999	VLDB	0.00017965707
692	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.00014919816
901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013334162
1,900	StatiX: Making XML Count	2002	SIGMOD	9.5168326e-05
2,326	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD	8.748172e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,625	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
2	12,555	Relational-Style XML Query	2008	SIGMOD
3	2,817	On the minimization of XPath queries	2003	VLDB
4	2,472	Path Queries on Compressed XML	2003	VLDB
5	901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB
6	12,534	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
7	8,066	Semantic Query Optimization for XQuery over XML Streams	2005	VLDB
8	3,167	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB
9	3,180	Approximate XML Query Answers	2004	SIGMOD
10	2,326	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD