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

DOI10.1016/J.TCS.2007.02.062MaRDI QIDQ2373746zbMATH OpenOpenAlexFDO

Authors Martin Grohe, Christoph Koch, Nicole Schweikardt

Publication date 16 July 2007

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

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

zbMATH Keywords

lower boundsdata streamsexternal memoryXML query languagesmachine models

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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

Describes a project that uses

Uses Software

• XPath
• XQuery

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)