Continuous monitoring of ${\ell }_p$ norms in data streams

Abstract

In insertion-only streaming, one sees a sequence of indices $a_1,a_2,\dots ,a_m\in [n]$. The stream defines a sequence of $m$ frequency vectors $x^{(1)},\dots ,x^{(m)}\in {\mathbb{R}}^n$ with $(x^{(t)}{)}_i=|\{j:j\in [t],a_j=i\}|$. That is, $x^{(t)}$ is the frequency vector after seeing the first $t$ items in the stream. Much work in the streaming literature focuses on estimating some function $f(x^{(m)})$. Many applications though require obtaining estimates at time $t$ of $f(x^{(t)})$, for every $t\in [m]$. Naively this guarantee is obtained by devising an algorithm with failure probability $\ll 1/m$, then performing a union bound over all stream updates to guarantee that all $m$ estimates are simultaneously accurate with good probability. When $f(x)$ is some ${\ell }_p$ norm of $x$, recent works have shown that this union bound is wasteful and better space complexity is possible for the continuous monitoring problem, with the strongest known results being for $p=2$ [HTY14, BCIW16, BCINWW17]. In this work, we improve the state of the art for all $0<p<2$, which we obtain via a novel analysis of Indyk's $p$-stable sketch [Indyk06].

arXiv commentv2: Lemma 10 proof now correctly bounds q <= (1/eps)^{O(1/p}) instead of the previously erroneous 1/eps^4. All stated results still hold for p in (0,2] bounded away from zero

Cited by in corpus (1)

• A Framework for Adversarially Robust Streaming Algorithms