Campus Event Calendar
Event Entry
What and Who
The Complexity of Querying External Memory and Streaming Data
Prof. Dr. Nicole Schweikardt
Informatik-Kolloquium
AG 1, AG 2, AG 3, AG 4, AG 5
Expert Audience
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 11 November 2005
16:00
-- Not specified --
45 - FR 6.2
Hörsaal 1
Saarbrücken
Abstract
We introduce a computation model for streaming and external memory data that distinguishes between sequentially reading (streaming) data from external memory (through main memory) and randomly accessing external memory data at specific memory locations. It is well-known that the latter is much more expensive in practice. We explain how a number of lower bound results are obtained in this model and how they can be applied for proving lower bounds for XML query processing. In the scenario with a single external memory device, strong lower bounds can be obtained by using techniques from communication complexity. To prove tight lower bounds for a setting where two or more external memory devices are available, we simulate computations by non-uniform models called list-machines, for which we can establish lower bounds by combinatorial means.
This is joint work with Martin Grohe, Andre Hernich, and Christoph Koch.
This is joint work with Martin Grohe, Andre Hernich, and Christoph Koch.
Contact
--email hidden
passcode not visible
logged in users only
Veronika Weinand, 11/08/2005 12:24 -- Created document.