Streaming sums in sublinear space

Vladimir Braverman, Stephen R. Chestnut

Introduction

In the field of data streaming, algorithms are designed to process massive sequences of updates using minimal memory. While approximating "positive moments" ($F_p = \sum |f_d|^p$ for $p > 0$) has been a cornerstone of streaming theory for decades, "negative moments" ($p < 0$) and other decreasing functions remained largely unexplored. In their paper, "Universal sketches for the frequency negative moments and other decreasing streaming sums," Vladimir Braverman and Stephen R. Chestnut provide a theoretical breakthrough by characterizing the space complexity required to approximate a broad class of functions where small values contribute significantly to the total sum.

The Challenge of Decreasing Functions

In standard streaming problems, such as estimating the number of distinct elements or high-frequency items, we typically focus on the "heavy hitters"—items with large frequencies. However, for negative moments and other non-increasing functions $g$, the logic is inverted: items with low frequencies dominate the sum.

In a typical stream, infrequent items are often treated as noise. In this context, that noise is the signal. The authors address the general problem of approximating $\sum g(|f_d|)$ where $g$ is any non-negative, non-increasing function. This includes elusive metrics like the harmonic mean and negative frequency moments, answering a long-standing open question regarding the existence of "universal" sketches for these families of functions.

The $\sigma$ Parameter: A New Complexity Measure

The authors identify a single parameter, $\sigma(\epsilon, g, m, n)$, that dictates the memory requirements for these problems. This parameter is derived from a nonlinear optimization problem:

$$\sigma \approx \max \{ |supp(f)| : f \in \mathcal{F}, g(f) \leq \epsilon^{-1}g(1) \}$$

Essentially, $\sigma$ represents the maximum number of items the stream can contain such that no single item's contribution overwhelms the $(1 \pm \epsilon)$-approximation. This parameter serves as both the foundation for their upper bounds and the basis for their lower bound proofs.

Algorithmic Approach and Universality

The core of the proposed solution is a sampling-based algorithm. Unlike traditional sketches that might be tailored to a specific $p$-moment, this approach uses pairwise independent sampling.

Key Techniques:

  • Sampling Strategy: The algorithm samples items from the stream with a probability $q$ derived from $\sigma$. When an item is sampled, its frequency is tracked exactly.
  • Universal Sketching: A significant contribution of this work is the "universal" property of the sketch. Because the sampling probability depends on the complexity parameter $\sigma$ rather than the specific shape of the function $g$, a single sketch can provide approximations for any decreasing function $g'$ that is "no harder" than the original $g$ (i.e., has a smaller or equal $\sigma$).
  • The Heavy Hitter Inversion: The authors redefine the concept of an $\epsilon$-heavy hitter. In this framework, an item $d$ is a heavy hitter if $g(f_d) \geq \epsilon g(f)$. Because $g$ is decreasing, these heavy hitters are often the items with the smallest frequencies.

Theoretical Results

The authors establish nearly optimal space bounds for different streaming models:

  1. Turnstile Streams: The space complexity is characterized as $O(\epsilon^{-1}\sigma \log^2 n \log M)$ bits.
  2. Insertion-Only Streams: The complexity is reduced to $O(\epsilon^{-1}\sigma \log M + \log^2 n)$ bits.
  3. Negative Moments: For the specific case of $F_p$ where $p < 0$, they show the complexity is proportional to $\min\{n, \epsilon^{-1/(1-p)} m^{-p/(1-p)}\}$.

To prove these bounds are nearly optimal, the authors use reductions from Communication Complexity—specifically the "Disjointness" problem—to show that any approximating algorithm requires at least $\Omega(\sigma)$ bits.

Conclusion and Future Directions

This work provides the first precise space complexity for approximating the harmonic mean and negative moments in a stream, partially answering a 2009 open question by Jelani Nelson regarding the limits of universal sketching.

While the paper establishes a robust theoretical framework, some practical hurdles remain. The optimal algorithm currently requires a priori knowledge of $m$ (the total sum of frequencies) to calculate $\sigma$. While the authors suggest using parallel estimators to mitigate this, a truly one-pass, $m$-agnostic optimal sketch is a potential area for future refinement. Additionally, a small logarithmic gap remains between the lower and upper bounds, and extending these "universal" properties to non-monotonic functions remains a significant challenge for the field.

Summary updated

BibTeX
@inproceedings{braverman2015streaming,
  author = {Vladimir Braverman and Stephen R. Chestnut},
  title = {{Streaming sums in sublinear space}},
  booktitle = {APPROX-RANDOM},
  year = {2015},
  doi = {10.4230/lipics.approx-random.2015.591},
}
Figure