Computing on data streams
Monika Rauch Henzinger, Prabhakar Raghavan, Sridhar Rajagopalan · DIMACS series in discrete mathematics and theoretical computer science · 1999
In this paper we study the space requirement of algorithms that make only one (or a small number of) pass(es) over the input data. We study such algorithms under a model of data streams that we introduce here. We give a number of upper and lower bounds for problems stemming from queryprocessing, invoking in the process tools from the area of communication complexity. 1