Machine Models and Lower Bounds for Query Processing
Summary: Surveys machine models for massive-data query processing—extending classical data streams with limited internal memory plus multiple large read/write external streams—and proves communication-complexity-based lower bounds for standard query tasks. Compares read/write-streams to Finite Cursor Machines, StrSort, and the Parallel Disk Model to clarify implications for streaming and external-memory query algorithms. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,062 | Randomized Multi-pass Streaming Skyline Algorithms | 2009 | VLDB | 5.7268277e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 43 | Models and Issues in Data Stream Systems | 2002 | PODS | 0.00072723062 |
| 1,356 | Validating Streaming XML Documents | 2002 | PODS | 0.0001239231 |
| 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,695 | On the Memory Requirements of XPath Evaluation over XML Streams | 2004 | PODS | 6.8345021e-05 |
| 5,248 | Buffering in Query Evaluation over XML Streams | 2005 | PODS | 5.6056584e-05 |
| 5,979 | External Memory Algorithms | 1998 | PODS | 5.2450009e-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
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,717 | Approximate Join Processing Over Data Streams | 2003 | SIGMOD | 0.00010793312 |
| 13,040 | Query Processing on Personal Computers: A Pragmatic Approach (Extended Abstract) | 1984 | VLDB | 4.1945683e-05 |
| 194 | Query Processing, Resource Management, and Approximation in a Data Stream Management System | 2003 | CIDR | 0.00035426067 |
| 9,632 | External Memory Stream Sampling | 2015 | PODS | 4.313481e-05 |
| 12,489 | Randomized Computations on Large Data Sets: Tight Lower Bounds | 2006 | PODS | 4.1945683e-05 |
| 1,904 | Characterizing Memory Requirements for Queries over Continuous Data Streams | 2002 | PODS | 0.00010154528 |
| 1,222 | Querying and Mining Data Streams: You Only Get One Look | 2002 | SIGMOD | 0.00013213129 |
| 12,530 | Lower Bounds for Sorting with Few Random Accesses to External Memory | 2005 | PODS | 4.1945683e-05 |
| 13,483 | Theory of Data Stream Computing: Where to Go | 2011 | PODS | - |
| 43 | Models and Issues in Data Stream Systems | 2002 | PODS | 0.00072723062 |