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.