2012/12/18 by Beame, Paul, Clifford, Raphael, Machmouchi, Widad
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1212.4372
We consider time-space tradeoffs for exactly computing frequency moments and order statistics over sliding windows. Given an input of length 2n-1, the task is to output the function of each window of length n, giving n outputs in total. Computations over sliding windows are related to direct sum problems except that inputs to instances almost completely overlap. We show an average case and randomized time-space tradeoff lower bound of TS in Omega(n2) for multi-way branching programs, and hence standard RAM and word-RAM models, to compute the number of distinct elements, F0, in sliding windows over alphabet [n]. The same lower bound holds for computing the low-order bit of F0 and computing any frequency moment Fk for k not equal to 1. We complement this lower bound with a TS in O(n2) deterministic RAM algorithm for exactly computing Fk in sliding windows. We show time-space separations between the complexity of sliding-window element distinctness and that of sliding-window F0\bmod 2 computation. In particular for alphabet [n] there is a very simple errorless sliding-window algorithm for element distinctness that runs in O(n) time on average and uses O(logn) space. We show that any algorithm for a single element distinctness instance can be extended to an algorithm for the sliding-window version of element distinctness with at most a polylogarithmic increase in the time-space product. Finally, we show that the sliding-window computation of order statistics such as the maximum and minimum can be computed with only a logarithmic increase in time, but that a TS in Omega(n2) lower bound holds for sliding-window computation of order statistics such as the median, a nearly linear increase in time when space is small.