Personal tools
You are here: Home Events Abstract Archives 2005 Tight Lower Bounds for Query Processing on Streaming and External Memory Data

Tight Lower Bounds for Query Processing on Streaming and External Memory Data

Martin Grohe Institut fur Informatik Humboldt-University, Berlin 2pm Friday 6th May 2005 Room 2511, JCMB, King's Buildings

We consider a scenario where we want to query a large dataset that is stored in external memory and does not fit into main memory. The most constrained resources in such a situation are the size of the main memory and the number of random accesses to external memory. We note that sequentially streaming data from external memory through main memory is much less prohibitive than random access.

We propose an abstract model of this scenario in which we restrict the size of the main memory and the number of random accesses to external memory, but do not restrict sequential reads. A distinguishing feature of our model is that it admits the usage of auxiliary external memory for storing intermediate results, such as several hard disks that can be accessed in parallel.

In the setting without auxiliary external memory, we prove tight lower bounds for XPATH-processing. These are based on fairly simple techniques from communication complexity. In the setting with auxiliary external memory, we prove lower bounds for sorting. The techniques from communication complexity are not applicable here. Instead, we simulate our model by a new non-uniform computation model for which we can establish the lower bounds by combinatorial means.

Joint work with Christoph Koch and Nicole Schweikardt.

Document Actions