Tight lower bounds for query processing on streaming and external memory data

DOI10.1016/J.TCS.2007.02.062zbMATH Open1118.68051arXivcs/0505002OpenAlexW2149268219MaRDI QIDQ2373746FDOQ2373746

Authors: Martin Grohe, Christoph Koch, Nicole Schweikardt 

Publication date: 16 July 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/cs/0505002

Recommendations

• Automata, Languages and Programming
• Fundamentals of Computation Theory
• New unbounded verifiable data streaming for batch query with almost optimal overhead
• On (dynamic) range minimum queries in external memory
• Lower bounds for processing data with few random accesses to external memory
• Efficient external memory structures for range-aggregate queries

zbMATH Keywords

lower boundsdata streamsexternal memoryXML query languagesmachine models

Mathematics Subject Classification ID

Data structures (68P05) Database theory (68P15)

Cites Work

• The space complexity of approximating the frequency moments
• Title not available (Why is that?)
• Title not available (Why is that?)
• Query automata over finite trees
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Expressiveness of structured document query languages based on attribute grammars
• Data streams: algorithms and applications.
• Communication Complexity
• Monadic Datalog and the expressive power of languages for web information extraction
• Reversal Complexity
• Reversal complexity revisited
• Title not available (Why is that?)
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Title not available (Why is that?)
• Lower bounds on communication complexity
• Selection and sorting with limited storage
• Tree acceptors and some of their applications
• Database Theory - ICDT 2005
• On the memory requirements of XPath evaluation over XML streams
• Some Results on Tape-Bounded Turing Machines
• Algorithms for memory hierarchies. Advanced lectures
• Title not available (Why is that?)
• Automata, Languages and Programming
• Fundamentals of Computation Theory

Cited In (7)

• Fundamentals of Computation Theory
• Reversal complexity revisited
• Lower bounds for processing data with few random accesses to external memory
• Streamability of nested word transductions
• Memory lower bounds for XPath evaluation over XML streams
• Automata, Languages and Programming
• Efficient data storage and retrieval organization using the frequency properties of the query stream

Uses Software

• XQuery
• XPath

This page was built for publication: Tight lower bounds for query processing on streaming and external memory data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373746)