Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-178 | 29th March 2013 22:39

Sliding Windows With Limited Storage

RSS-Feed




Revision #1
Authors: Paul Beame, Raphael Clifford, Widad Machmouchi
Accepted on: 29th March 2013 22:39
Downloads: 2483
Keywords: 


Abstract:

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}


Paper:

TR12-178 | 18th December 2012 16:23

Sliding Windows With Limited Storage


Abstract:

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}



ISSN 1433-8092 | Imprint