SRC Technical Note 1998-011

Computing on Data Streams

Monika Rauch Henzinger, Prabhakar Raghavan, Sridar Rajagopalan

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 query-processing, invoking in the process tools from the area of communication complexity.

Back to the SRC Technical Notes main page.

• PostScript compressed with UNIX compress -- 160 Kbytes
  
• PostScript compressed with GNU compress (gzip) -- 152 Kbytes
  
• PostScript compressed with ZIP -- 152 Kbytes
  
• PostScript -- 288 Kbytes
  
• Portable Document Format (PDF) -- 73 Kbytes