The complexity of querying external memory and streaming data

Abstract. We review a recently introduced computation model for streaming and external memory data. An important feature of this model is that it 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.