Lower bounds for processing data with few random accesses to external memory

DOI10.1145/1516512.1516514zbMATH Open1325.68098OpenAlexW2004196714MaRDI QIDQ3452210FDOQ3452210

Authors: Martin Grohe, André Hernich, Nicole Schweikardt 

Publication date: 11 November 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1516512.1516514

Recommendations

• Tight lower bounds for query processing on streaming and external memory data
• Fundamentals of Computation Theory
• Automata, Languages and Programming
• Lower bounds for external algebraic decision trees
• External Sampling

zbMATH Keywords

XMLcomplexitydata streamsquery processingquery optimizationreal-time datasemi-structured data

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)

Cited In (3)

• Tight lower bounds for query processing on streaming and external memory data
• Fundamentals of Computation Theory
• Automata, Languages and Programming

This page was built for publication: Lower bounds for processing data with few random accesses to external memory

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