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

DOI10.1016/j.tcs.2007.02.062zbMath1118.68051arXivcs/0505002OpenAlexW2149268219MaRDI QIDQ2373746

Nicole Schweikardt, Martin Grohe, Christoph Koch

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

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

Related Items (4)

Memory lower bounds for XPath evaluation over XML streams ⋮ Reversal complexity revisited ⋮ Unnamed Item ⋮ On the Value of Multiple Read/Write Streams for Data Compression

Uses Software

• XQuery
• XPath

Cites Work

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

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