DBScholar

Back to papers

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)

Paper ID
1413
Venue
PODS
Year
2007
Pagerank
5.4153038e-05
Overall Rank
8,488 | 41.77%
DOI
10.1145/1265530.1265537

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{schweikardt_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{Machine Models and Lower Bounds for Query Processing}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265537},
        doi = {10.1145/1265530.1265537},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Schweikardt, Nicole},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank Citing Paper Year Venue Pagerank
4,941 Randomized Multi-pass Streaming Skyline Algorithms 2009 VLDB 6.4333573e-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
26 Models and Issues in Data Stream Systems 2002 PODS 0.00052982574
1,758 Validating Streaming XML Documents 2002 PODS 9.8162828e-05
2,132 The Complexity of XPath Query Evaluation 2003 PODS 9.119436e-05
2,625 Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach 2003 VLDB 8.3300135e-05
3,659 On the Memory Requirements of XPath Evaluation over XML Streams 2004 PODS 7.2176232e-05
5,247 Buffering in Query Evaluation over XML Streams 2005 PODS 6.3009176e-05
6,289 External Memory Algorithms 1998 PODS 5.9261616e-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
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,397 Approximate Join Processing Over Data Streams 2003 SIGMOD
2 13,239 Query Processing on Personal Computers: A Pragmatic Approach (Extended Abstract) 1984 VLDB
3 150 Query Processing, Resource Management, and Approximation in a Data Stream Management System 2003 CIDR
4 9,732 External Memory Stream Sampling 2015 PODS
5 12,682 Randomized Computations on Large Data Sets: Tight Lower Bounds 2006 PODS
6 1,656 Characterizing Memory Requirements for Queries over Continuous Data Streams 2002 PODS
7 1,274 Querying and Mining Data Streams: You Only Get One Look 2002 SIGMOD
8 12,723 Lower Bounds for Sorting with Few Random Accesses to External Memory 2005 PODS
9 13,682 Theory of Data Stream Computing: Where to Go 2011 PODS
10 26 Models and Issues in Data Stream Systems 2002 PODS