New Characterizations in Turnstile Streams with Applications

Yuqing Ai, Wei Hu, Yi Li, David P. WoodruffComputational Complexity Conference 2016 · OpenReview

TL;DR

This paper significantly strengthens a foundational result in streaming algorithms, showing that many streaming problems can be solved by maintaining a "linear sketch" of the data. The authors remove key limitations of previous work, enabling new lower bounds for important problems like additive error norm approximation and resolving open questions in dynamic graph streams.

What Problem Does This Paper Address?

Streaming algorithms process massive datasets using limited memory. A key question is understanding the fundamental space complexity of computing functions on these streams. A prior work (Li et al., STOC'14) established a powerful reduction: any 1-pass streaming algorithm for a broad class of problems can be implemented using a "linear sketch" (specifically, $Ax \pmod q$). This meant that proving lower bounds for linear sketches was equivalent to proving lower bounds for these streaming problems.

However, this reduction had several limitations:

  1. The "Box Constraint": It only applied to algorithms that were guaranteed to be correct if the data values stayed within a certain range ($[-m, m]$) at the end of the stream, even if they temporarily exceeded this range during the stream. This is often an unrealistic assumption.
  2. Negative Coordinates: The reduction didn't directly apply to the "strict turnstile model" where data values are always non-negative, which is common in graph problems.
  3. 1-Pass Restriction: It was limited to algorithms that made only a single pass over the data, while some problems benefit from multiple passes.

This paper aims to overcome these limitations, providing a more general characterization of streaming algorithms and unlocking new applications and lower bounds.

Methods

The authors introduce several key technical advancements:

  • Removing the Box Constraint: They provide a condition (specifically, when the algorithm's space complexity is small, $O(\log m / n)$) under which the reduction to linear sketches holds even if the data values are guaranteed to stay within $[-m, m]$ at all times during the stream. This is crucial for proving lower bounds in more natural settings.
  • Strict Turnstile Model Equivalence: They establish an equivalence between general 1-pass algorithms and linear sketches in the strict turnstile model (where data values are always non-negative). This is achieved by adapting the reduction to handle non-negative inputs.
  • Multi-Pass Extension: They extend the reduction to algorithms that make multiple passes. The key idea is that a $p$-pass algorithm can be reduced to a sequence of $p$ linear sketches, where each sketch is chosen based on the output of the previous pass.

These technical improvements are built upon the framework of stream automata and simultaneous communication complexity, leveraging concepts like path-reversible and path-independent automata.

Datasets

Not discussed in the paper. The paper focuses on theoretical characterizations and lower bounds for abstract data stream models, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • The "Box Constraint" is often unnecessary: The paper shows that for space-efficient algorithms, the strict requirement of staying within $[-m, m]$ at all times is sufficient for the linear sketch reduction, not just at the end. This is a significant relaxation.
  • Linear Sketches are fundamental even for non-negative data: The equivalence in the strict turnstile model means that understanding linear sketches is key to understanding algorithms for problems like dynamic graph streams, where non-negativity is natural.
  • Multi-pass algorithms don't fundamentally break the sketch paradigm: The reduction to multi-pass sketches suggests that even with multiple passes, the core idea of linear sketching remains relevant for characterizing optimal algorithms.
  • New Lower Bounds for Additive Error: By removing the box constraint, the authors derive the first super-constant $\Omega(\log m)$ lower bounds for approximating norms with additive error, a weaker but often more practical form of approximation. This is particularly important for $p$-norms where $1 \le p \le 2$.

Key Results

  • Removal of Box Constraint: A condition is given under which the reduction to linear sketches holds without the "box constraint" (i.e., data values are bounded at all times).
  • Strict Turnstile Model Equivalence: A 1-pass algorithm in the strict turnstile model (non-negative values) is equivalent to a linear sketch.
  • Resolution of Dynamic Graph Matching: This result, combined with prior work, resolves the 1-pass space complexity for approximating maximum matching in dynamic graph streams.
  • Multi-Pass Reduction: A $p$-pass randomized automaton can be reduced to a $p$-pass path-independent automaton without increasing space complexity.
  • New Lower Bounds:
    • $\Omega(\log m)$ lower bound for maintaining a counter with additive error $\epsilon m$.
  • $\Omega(\log m)$ lower bound for additive approximation of $l_p$-norms (tight for $1 \le p \le 2$).

Limitations and Future Work

  • The "Box Constraint" Removal Condition: The condition for removing the box constraint ($S(A, m) < c \cdot \log m$) is restrictive. The paper notes that this is tight, meaning algorithms with larger space might still require the box constraint for the reduction to work.
  • Communication Complexity Gap: For additive error norm approximation, the paper provides a lower bound using their new techniques but notes they don't know how to achieve this bound using traditional communication complexity arguments. This suggests potential for further theoretical exploration.
  • Multi-Pass Automata: While the reduction to multi-pass sketches is shown, the exact space complexity implications for specific multi-pass algorithms might still require further investigation.
  • Generalizing Applications: The paper demonstrates applications to norm approximation and graph matching. Future work could explore other streaming problems where these new characterizations might yield significant results.

Summary updated

Abstract

Recently, [Li, Nguyen, Woodruff, STOC 2014] showed any 1-pass constant probability streaming algorithm for computing a relation f on a vector x in {-m, -(m-1), ..., m}^n presented in the turnstile data stream model can be implemented by maintaining a linear sketch Ax mod q, where A is an r times n integer matrix and q = (q_1, ..., q_r) is a vector of positive integers. The space complexity of maintaining Ax mod q, not including the random bits used for sampling A and q, matches the space of the optimal algorithm. We give multiple strengthenings of this reduction, together with new applications. In particular, we show how to remove the following shortcomings of their reduction: 1. The Box Constraint. Their reduction applies only to algorithms that must be correct even if x_{infinity} = max_{i in [n]} |x_i| is allowed to be much larger than m at intermediate points in the stream, provided that x is in {-m, -(m-1), ..., m}^n at the end of the stream. We give a condition under which the optimal algorithm is a linear sketch even if it works only when promised that x is in {-m, -(m-1), ..., m}^n at all points in the stream. Using this, we show the first super-constant Omega(log m) bits lower bound for the problem of maintaining a counter up to an additive epsilon*m error in a turnstile stream, where epsilon is any constant in (0, 1/2). Previous lower bounds are based on communication complexity and are only for relative error approximation; interestingly, we do not know how to prove our result using communication complexity. More generally, we show the first super-constant Omega(log(m)) lower bound for additive approximation of l_p-norms; this bound is tight for p in [1, 2]. 2. Negative Coordinates. Their reduction allows x_i to be negative while processing the stream. We show an equivalence between 1-pass algorithms and linear sketches Ax mod q in dynamic graph streams, or more generally, the strict turnstile model, in which for all i in [n], x_i is nonnegative at all points in the stream. Combined with [Assadi, Khanna, Li, Yaroslavtsev, SODA 2016], this resolves the 1-pass space complexity of approximating the maximum matching in a dynamic graph stream, answering a question in that work. 3. 1-Pass Restriction. Their reduction only applies to 1-pass data stream algorithms in the turnstile model, while there exist algorithms for heavy hitters and for low rank approximation which provably do better with multiple passes. We extend the reduction to algorithms which make any number of passes, showing the optimal algorithm is to choose a new linear sketch at the beginning of each pass, based on the output of previous passes.
BibTeX
@inproceedings{ai2016new,
  author = {Yuqing Ai and Wei Hu and Yi Li and David P. Woodruff},
  title = {{New Characterizations in Turnstile Streams with Applications}},
  booktitle = {Computational Complexity Conference},
  year = {2016},
  url = {https://openreview.net/forum?id=PhSr7A1Z_S},
}
Figure