On the Memory Requirements of XPath Evaluation over XML Streams

Summary: First systematic communication-complexity lower bounds on memory for XPath stream evaluation, via new graph-theoretic query invariants; bounds hold even for filtering. Also provides a nearly matching, space‑optimal filtering algorithm that avoids automata/transducers. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1319
Venue: PODS
Year: 2004
Pagerank: 7.2176232e-05
Overall Rank: 3,659 | 74.90%
DOI: 10.1145/1055558.1055584

Incoming Non-self Citations Over Time

Authors

1. Ziv Bar-Yossef (IBM Almaden)
2. Marcus Fontoura (IBM Almaden)
3. Vanja Josifovski (IBM Almaden)

BibTeX Citation

@inproceedings{baryossef_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{On the Memory Requirements of XPath Evaluation over XML Streams}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055584},
        doi = {10.1145/1055558.1055584},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bar-Yossef, Ziv and Fontoura, Marcus and Josifovski, Vanja},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,107	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	6.8973582e-05
5,247	Buffering in Query Evaluation over XML Streams	2005	PODS	6.3009176e-05
7,480	The GCX System: Dynamic Buffer Minimization in Streaming XQuery Evaluation	2007	VLDB	5.6081446e-05
8,488	Machine Models and Lower Bounds for Query Processing	2007	PODS	5.4153038e-05
12,633	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD	5.093636e-05
12,682	Randomized Computations on Large Data Sets: Tight Lower Bounds	2006	PODS	5.093636e-05
12,723	Lower Bounds for Sorting with Few Random Accesses to External Memory	2005	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
236	Efficient Filtering of XML Documents for Selective Dissemination of Information	2000	VLDB	0.00023721569
738	Stream Processing of XPath Queries with Predicates	2003	SIGMOD	0.00014484337
928	XPath Queries on Streaming Data	2003	SIGMOD	0.00013153017
1,656	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS	0.00010097487
2,132	The Complexity of XPath Query Evaluation	2003	PODS	9.119436e-05
2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	8.0195639e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,576	Efficient Evaluation of XQuery over Streaming Data	2005	VLDB
2	12,534	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
3	2,132	The Complexity of XPath Query Evaluation	2003	PODS
4	2,625	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
5	2,817	On the minimization of XPath queries	2003	VLDB
6	666	Efficient Algorithms for Processing XPath Queries	2002	VLDB
7	738	Stream Processing of XPath Queries with Predicates	2003	SIGMOD
8	928	XPath Queries on Streaming Data	2003	SIGMOD
9	12,633	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD
10	5,247	Buffering in Query Evaluation over XML Streams	2005	PODS