Revision #1 Authors: Paul Beame, Raphael Clifford, Widad Machmouchi

Accepted on: 29th March 2013 22:39

Downloads: 2524

Keywords:

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

$T\cdot S \in \Omega(n^2)$ for multi-way branching programs, and

hence standard RAM and word-RAM models, to compute the number

of distinct elements, $F_0$, in sliding windows over alphabet $[n]$.

The same lower bound holds for computing the low-order bit of $F_0$ and

computing any frequency moment $F_k$ for $k\ne 1$.

We complement this lower bound with a $T\cdot S \in \tilde O(n^2)$

deterministic RAM algorithm for exactly computing $F_k$ in sliding windows.

We show time-space separations between the complexity of sliding-window element distinctness and that of sliding-window $F_0\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(\log{n})$ 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 $T\cdot S \in \Omega(n^2)$ lower

bound holds for sliding-window computation of order statistics such as the

median, a nearly linear increase in time when space is small.

\end{itemize}

TR12-178 Authors: Paul Beame, Raphael Clifford, Widad Machmouchi

Publication: 20th December 2012 16:21

Downloads: 2994

Keywords:

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

$T\cdot S \in \Omega(n^2)$ for multi-way branching programs, and

hence standard RAM and word-RAM models, to compute the number

of distinct elements, $F_0$, in sliding windows over alphabet $[n]$.

The same lower bound holds for computing the low-order bit of $F_0$ and

computing any frequency moment $F_k$ for $k\ne 1$.

We complement this lower bound with a $T\cdot S \in \tilde O(n^2)$

deterministic RAM algorithm for exactly computing $F_k$ in sliding windows.

We show time-space separations between the complexity of sliding-window element distinctness and that of sliding-window $F_0\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(\log{n})$ 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 $T\cdot S \in \Omega(n^2)$ lower

bound holds for sliding-window computation of order statistics such as the

median, a nearly linear increase in time when space is small.

\end{itemize}