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

Martin Grohe, Christoph Koch, Nicole Schweikardt

We study a clean machine model for external memory and stream processing. We show that the number of scans of the external data induces a strict hierarchy (as long as work space is…