## Abstract

We consider time-space tradeoffs for exactly computing frequency

moments and order statistics over sliding windows~\cite{dgim: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 the 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.

Using this reduction we present a family of randomized algorithms for

sliding-window element distinctness

with a heuristic analysis of $T^2\cdot S\in \tilde O(n^3)$, which

is strictly smaller than our lower bound

for sliding-window $F_0\bmod 2$ for $S$ smaller than $n/\mathrm{polylog} (n)$.

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.

moments and order statistics over sliding windows~\cite{dgim: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 the 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.

Using this reduction we present a family of randomized algorithms for

sliding-window element distinctness

with a heuristic analysis of $T^2\cdot S\in \tilde O(n^3)$, which

is strictly smaller than our lower bound

for sliding-window $F_0\bmod 2$ for $S$ smaller than $n/\mathrm{polylog} (n)$.

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.

Original language | English |
---|---|

Title of host publication | 2013 IEEE 54th Annual Symposium on Foundations of Computer Science |

Pages | 290-299 |

Publication status | Published - 27 Oct 2013 |