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)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 7 of 7 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,117 | Processing Queries on Tree-Structured Data Efficiently | 2006 | PODS | 7.5407318e-05 |
| 5,248 | Buffering in Query Evaluation over XML Streams | 2005 | PODS | 5.6056584e-05 |
| 7,454 | The GCX System: Dynamic Buffer Minimization in Streaming XQuery Evaluation | 2007 | VLDB | 4.7263711e-05 |
| 8,241 | Machine Models and Lower Bounds for Query Processing | 2007 | PODS | 4.5519176e-05 |
| 12,439 | Efficient Algorithms for Evaluating XPath over Streams | 2007 | SIGMOD | 4.1945683e-05 |
| 12,489 | Randomized Computations on Large Data Sets: Tight Lower Bounds | 2006 | PODS | 4.1945683e-05 |
| 12,530 | Lower Bounds for Sorting with Few Random Accesses to External Memory | 2005 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 7 | Optimal Aggregation Algorithms for Middleware [Extended Abstract] | 2001 | PODS | 0.0015496097 |
| 226 | Efficient Filtering of XML Documents for Selective Dissemination of Information | 2000 | VLDB | 0.00032431532 |
| 831 | Stream Processing of XPath Queries with Predicates | 2003 | SIGMOD | 0.00016171218 |
| 987 | XPath Queries on Streaming Data | 2003 | SIGMOD | 0.00014819204 |
| 1,848 | Typing and Querying XML Documents: Some Complexity Bounds | 2003 | PODS | 0.00010330772 |
| 1,904 | Characterizing Memory Requirements for Queries over Continuous Data Streams | 2002 | PODS | 0.00010154528 |
| 2,248 | The Complexity of XPath Query Evaluation | 2003 | PODS | 9.2038466e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,931 | Efficient Evaluation of XQuery over Streaming Data | 2005 | VLDB | 5.8207617e-05 |
| 12,340 | Efficient Rewriting of XPath Queries Using Query Set Specifications | 2009 | VLDB | 4.1945683e-05 |
| 2,248 | The Complexity of XPath Query Evaluation | 2003 | PODS | 9.2038466e-05 |
| 2,855 | Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach | 2003 | VLDB | 8.0059865e-05 |
| 3,084 | On the minimization of Xpath queries | 2003 | VLDB | 7.6011919e-05 |
| 713 | Efficient Algorithms for Processing XPath Queries | 2002 | VLDB | 0.00017731096 |
| 831 | Stream Processing of XPath Queries with Predicates | 2003 | SIGMOD | 0.00016171218 |
| 987 | XPath Queries on Streaming Data | 2003 | SIGMOD | 0.00014819204 |
| 12,439 | Efficient Algorithms for Evaluating XPath over Streams | 2007 | SIGMOD | 4.1945683e-05 |
| 5,248 | Buffering in Query Evaluation over XML Streams | 2005 | PODS | 5.6056584e-05 |