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: h6c1be1115056d10d
Venue: PODS
Year: 2004
Pagerank: 7.0557724e-05
Overall Rank: 3,746 | 74.82%
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,189	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	6.7459542e-05
5,368	Buffering in Query Evaluation over XML Streams	2005	PODS	6.1597369e-05
7,623	The GCX System: Dynamic Buffer Minimization in Streaming XQuery Evaluation	2007	VLDB	5.4823129e-05
8,656	Machine Models and Lower Bounds for Query Processing	2007	PODS	5.2938008e-05
12,923	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD	4.9793485e-05
12,972	Randomized Computations on Large Data Sets: Tight Lower Bounds	2006	PODS	4.9793485e-05
13,013	Lower Bounds for Sorting with Few Random Accesses to External Memory	2005	PODS	4.9793485e-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.0010679641
247	Efficient Filtering of XML Documents for Selective Dissemination of Information	2000	VLDB	0.00023199427
760	Stream Processing of XPath Queries with Predicates	2003	SIGMOD	0.00014161342
958	XPath Queries on Streaming Data	2003	SIGMOD	0.00012860244
1,666	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS	9.9382031e-05
2,177	The Complexity of XPath Query Evaluation	2003	PODS	8.9153711e-05
2,934	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	7.839851e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,677	Efficient Evaluation of XQuery over Streaming Data	2005	VLDB
2	12,824	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
3	2,177	The Complexity of XPath Query Evaluation	2003	PODS
4	2,680	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
5	2,881	On the minimization of XPath queries	2003	VLDB
6	679	Efficient Algorithms for Processing XPath Queries	2002	VLDB
7	760	Stream Processing of XPath Queries with Predicates	2003	SIGMOD
8	958	XPath Queries on Streaming Data	2003	SIGMOD
9	12,923	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD
10	5,368	Buffering in Query Evaluation over XML Streams	2005	PODS