Time Bounds for Streaming Problems

We give tight cell-probe bounds for the time to compute convolution, multiplication and Hamming distance in a stream. The cell probe model is a particularly strong computational model and subsumes, for example, the popular word RAM model. We first consider online convolution where the task is to compute the inner product between a fixed n-dimensional vector and a vector of the n most recent values from a stream. One symbol of the stream arrives at a time and then each output symbol must be computed before the next input symbol arrives. Next we show bounds for online multiplication of two n-digit numbers where one of the multiplicands is known in advance and the other arrives one digit at a time, starting from the lower-order end. When a digit arrives, the task is to compute a single new digit from the product before the next digit arrives. Finally we look at the online Hamming distance problem where the Hamming distance is computed instead of the inner product. For each of these three problems, we give a lower bound of Omega ((delta/w) log n) time on average per output symbol, where delta is the number of bits needed to represent an input symbol and w is the cell or word size. We argue that these bounds are in fact tight within the cell probe model.