Data Stream Algorithmics
S. Muthukrishnan, (AT&T and Rutgers Univ), firstname.lastname@example.org
Say Paul shows numbers 1 through N in some permuted order, but leaves out one (or two) of the numbers. Carole needs to determine the missing number(s). But Carole has the ability to memorize only a small set of the numbers she sees! As one would expect, it suffices for Carole to simply keep certain statistics on the input stream to solve this problem. This simple puzzle is an example of processing data streams. In many applications such as in IP traffic analysis and in Homeland Security, data arrives as a stream. Keeping certain statistics on the data stream helps solve a number of monitoring problems. The challenge is to design suitable algorithms for estimating these statistics within limited resources. I will present an idiosyncratic view of this emerging area of data stream algorithmics. I will also discuss how to abstract these solutions and concerns into data stream management systems.