Browse/search for people

Publication - Dr Raphael Clifford

    Element distinctness, frequency moments, and sliding windows

    Citation

    Beame, P, Clifford, R & Machmouchi, W, 2013, ‘Element distinctness, frequency moments, and sliding windows’. in: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science., pp. 290-299

    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.

    Full details in the University publications repository