Tight Lower Bounds for Query Processing on Streaming and External Memory Data

Simple item page
dc.creatorGrohe, Martin
dc.creatorKoch, Christoph
dc.creatorSchweikardt, Nicole
dc.date2005-04-29
dc.date.accessioned2026-07-07T03:22:56Z
dc.date.available2026-07-07T03:22:56Z
dc.descriptionWe 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.
dc.description25 pages, 4 figures, to appear in Proc. ICALP 2005; extended version with appendix
dc.identifierhttps://arxiv.org/abs/cs/0505002
dc.identifierhttp://arxiv.org/abs/cs/0505002
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32751
dc.subjectDatabases
dc.subjectComputational Complexity
dc.subjectH.2.3; I.7.2
dc.titleTight Lower Bounds for Query Processing on Streaming and External Memory Data
dc.typetext

Files

Collections

arXiv