|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Tight Lower Bounds for Query Processing on Streaming and External Memory Data | | Martin Grohe
; Christoph Koch
; Nicole Schweikardt
; | | Date: |
30 Apr 2005 | | Subject: | Databases; Computational Complexity ACM-class: H.2.3; I.7.2 | cs.DB cs.CC | | Abstract: | We study a clean machine model for external memory and stream processing. We show that the number of scans of the external data induces a strict hierarchy (as long as work space is sufficiently small, e.g., polylogarithmic in the size of the input). We also show that neither joins nor sorting are feasible if the product of the number $r(n)$ of scans of the external memory and the size $s(n)$ of the internal memory buffers is sufficiently small, e.g., of size $o(sqrt[5]{n})$. We also establish tight bounds for the complexity of XPath evaluation and filtering. | | Source: | arXiv, cs.DB/0505002 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER