Buffering in Query Evaluation over XML Streams
Summary: Identifies two independent causes of large buffers in streaming XPath evaluation—full evaluation of queries with predicates and any evaluation of queries with multivariate predicates—and proves quantitative memory lower bounds using novel document properties. Shows these cases (with recursion) are essentially the only sources of superlinear buffering and provides algorithms matching the lower bounds for a significant XPath fragment. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,738 | AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering | 2006 | VLDB | 4.6636747e-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 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 11 of 11 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 |
| 43 | Models and Issues in Data Stream Systems | 2002 | PODS | 0.00072723062 |
| 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,264 | Projecting XML Documents | 2003 | VLDB | 0.00012976407 |
| 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 |
| 3,695 | On the Memory Requirements of XPath Evaluation over XML Streams | 2004 | PODS | 6.8345021e-05 |
| 3,925 | Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams | 2004 | VLDB | 6.6260709e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,209 | Scalable XML Query Processing using Parallel Pushdown Transducers | 2013 | VLDB | 4.3726599e-05 |
| 7,454 | The GCX System: Dynamic Buffer Minimization in Streaming XQuery Evaluation | 2007 | VLDB | 4.7263711e-05 |
| 2,248 | The Complexity of XPath Query Evaluation | 2003 | PODS | 9.2038466e-05 |
| 3,925 | Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams | 2004 | VLDB | 6.6260709e-05 |
| 4,931 | Efficient Evaluation of XQuery over Streaming Data | 2005 | VLDB | 5.8207617e-05 |
| 831 | Stream Processing of XPath Queries with Predicates | 2003 | SIGMOD | 0.00016171218 |
| 713 | Efficient Algorithms for Processing XPath Queries | 2002 | VLDB | 0.00017731096 |
| 12,439 | Efficient Algorithms for Evaluating XPath over Streams | 2007 | SIGMOD | 4.1945683e-05 |
| 987 | XPath Queries on Streaming Data | 2003 | SIGMOD | 0.00014819204 |
| 3,695 | On the Memory Requirements of XPath Evaluation over XML Streams | 2004 | PODS | 6.8345021e-05 |