Data Streams and Applications in Computer Science
David P. Woodruff · Bulletin of the European Association for Theoretical Computer Science · 2014
This is a short survey of my work in data streams and related applications, such as communication complexity, numerical linear algebra, and sparse recovery. The goal is give a non-technical overview of results in data streams, and highlight connections between these different areas. It is based on my Presburger lecture award given at ICALP, 2014. 1 The Data Stream Model Informally speaking, a data stream is a sequence of data that is too large to be stored in available memory. The data may be a sequence of numbers, points, edges in a graph, and so on. There are many examples of data streams, such as internet search logs, network traffic, sensor networks, and scientific data streams (such as in astronomics, genomics, physical simulations, etc.). The abundance of data streams has led to new algorithmic paradigms for processing them, which often impose very stringent requirements on the algorithm’s resources. Formally, in the streaming model, there is a sequence of elements a1, . . . , am presented to an algorithm, where each element is drawn from a universe [n] = {1, . . . , n}. The algorithm is allowed a single or a small number of passes over the stream. In network applications, the algorithm is typically only given a single pass, since if data on a network is not physically stored somewhere, it may be impossible to make a second pass over it. In other applications, such as when data resides on external memory, it may be streamed through main memory a small number of times, each time constituting a pass of the algorithm. The algorithm would like to compute a function or relation of the data stream. Because of the sheer size, for many interesting problems the algorithm is necessarily randomized and approximate in order to be efficient. One should note that the randomness is in the random coin tosses of the algorithm rather than in the stream. That is, with high probability over the coin tosses of the algorithm, the algorithm should correctly compute the function or relation for any stream that is presented to it. This is more robust than say, if the algorithm assumed particular orderings of the stream that could make the problem easier to solve. In this survey we focus on computing or approximating order-independent functions f (a1, . . . , am). A function is order-independent if applying any permutation to its inputs results in the same function value. As we will see, this is often the case in numerical applications, such as if one is interested in the number of distinct values in the sequence a1, . . . , am. One of the main goals of a streaming algorithm is to use as little memory as possible in order to compute or approximate the function of interest. The amount of memory used (in bits) is referred to as the space complexity of the algorithm. While it is always possible for the algorithm to store the entire sequence a1, . . . , am, this is usually extremely prohibitive in applications. For example, internet routers often have limited resources; asking them to store a massive sequence of network traffic is infeasible. Another goal of streaming algorithms is their processing time, i.e., how often it takes to update their memory contents when presented with a new item in the stream. Often items in streams are presented at very high speeds and the algorithm needs to quickly update the data structures in its memory in order to be ready to process future updates. For order-independent functions, we can think of the stream as an evolution of an underlying vector x ∈ Rn. That is, x is initialized to the all zero vector, and when the item i appears in the stream, x undergoes the update