Theory of Computing
-------------------
Title : Universal Streaming of Subset Norms
Authors : Vladimir Braverman, Robert Krauthgamer, and Lin F. Yang
Volume : 18
Number : 20
Pages : 1-32
URL : https://theoryofcomputing.org/articles/v018a020
Abstract
--------
Most known algorithms in the streaming model of computation aim to
approximate a single function such as an $\ell_p$ norm.
In 2009, Nelson [\url{https://sublinear.info}, Open Problem 30] asked
if it is possible to design _universal algorithms_, that
simultaneously approximate multiple functions of the stream. In this
paper we answer the question of Nelson for the class of
_subset-$\ell_0$ norms_ in the insertion-only frequency-vector model.
Given a family of subsets, $\calS\subset 2^{[n]}$, we provide a single
streaming algorithm that can $(1\pm \epsilon)$-approximate the
subset-$\ell_p$ norm for every $S\in\calS$. Here, the subset-$\ell_p$
norm of $v\in \R^n$ with respect to the set $S\subseteq [n]$ is the
$\ell_p$ norm of $v_{|S}$ (the vector $v$ restricted to $S$ by zeroing
all other coordinates).
Our main result is a nearly tight characterization of the space
complexity of the subset-$\ell_0$ norm for every family $\calS\subset
2^{[n]}$ in insertion-only streams, expressed in terms of the "heavy-
hitter dimension" of $\calS$, a new combinatorial quantity related to
the VC-dimension of $\calS$. We also show that the more general
turnstile and sliding-window models require a much larger space usage.
All these results easily extend to the $\ell_1$ norm.
In addition, we design algorithms for two other subset-$\ell_p$
variants. These can be compared to the famous Priority Sampling
algorithm of Duffield, Lund and Thorup [JACM 2007], which achieves
additive approximation $\epsilon\norm{v}_1$ for all possible subsets
($\calS=2^{[n]}$) in the entrywise update model. One of our algorithms
extends their algorithm to handle turnstile updates, and another one
achieves multiplicative approximation, given a family $\calS$.