Tracking the ${\ell }_2$ Norm with Constant Update Time

Abstract

The \emph{${\ell }_2$ tracking problem} is the task of obtaining a streaming algorithm that, given access to a stream of items $a_1,a_2,a_3,\dots$ from a universe $[n]$, outputs at each time $t$ an estimate to the ${\ell }_2$ norm of the \textit{frequency vector} $f^{(t)}\in {\mathbb{R}}^n$ (where $f_i^{(t)}$ is the number of occurrences of item $i$ in the stream up to time $t$). The previous work [Braverman-Chestnut-Ivkin-Nelson-Wang-Woodruff, PODS 2017] gave an streaming algorithm with (the optimal) space using $O({\epsilon }^{-2}\log (1/\delta ))$ words and $O({\epsilon }^{-2}\log (1/\delta ))$ update time to obtain an $\epsilon$-accurate estimate with probability at least $1-\delta$. We give the first algorithm that achieves update time of $O(\log 1/\delta )$ which is independent of the accuracy parameter $\epsilon$, together with the nearly optimal space using $O({\epsilon }^{-2}\log (1/\delta ))$ words. Our algorithm is obtained using the \textsf{CountSketch} of [Charilkar-Chen-Farach-Colton, ICALP 2002].

To appear in APPROX 2019