Asymptotically exact streaming algorithms

Marc Heinrich, Alexander Munteanu, Christian SohlerarXiv 2014 · OpenReview

Abstract

We introduce a new computational model for data streams: asymptotically exact streaming algorithms. These algorithms have an approximation ratio that tends to one as the length of the stream goes to infinity while the memory used by the algorithm is restricted to polylog(n) size. Thus, the output of the algorithm is optimal in the limit. We show positive results in our model for a series of important problems that have been discussed in the streaming literature. These include computing the frequency moments, clustering problems and least squares regression. Our results also include lower bounds for problems, which have streaming algorithms in the ordinary setting but do not allow for sublinear space algorithms in our model.

Introduction

In the era of massive data streams, the standard paradigm for algorithmic design has been the $(1 \pm \epsilon)$-approximation. Traditional streaming algorithms process data in a single pass with sublinear memory, providing a result within a fixed error margin $\epsilon$. However, this approach ignores a fundamental statistical intuition: as the sample size $n$ grows, our confidence and precision should naturally increase.

This paper introduces asymptotically exact streaming algorithms. These are algorithms where the approximation ratio $\alpha$ satisfies $\lim_{n \to \infty} \alpha = 1$. In other words, the error $\epsilon$ is not a fixed constant but a function $\epsilon(n)$ that shrinks toward zero as the stream progresses, all while maintaining a memory footprint of $O(\text{polylog } n)$.

The "Improving Precision" Strategy

To achieve asymptotic exactness, the authors adapt two foundational streaming techniques: Sketching (for frequency moments and regression) and Coresets (for clustering).

The core innovation is a meta-algorithmic strategy. Rather than maintaining a single summary with a static $\epsilon$, the algorithm periodically initializes new sketches or coresets with increasingly higher precision (smaller $\epsilon_i$). By carefully balancing the number of active summaries, the algorithm can transition to more precise estimates as the stream length $n$ provides sufficient data to justify the increased memory cost of higher precision, without ever exceeding the polylogarithmic memory bound.

Clustering and Objective Functions

The paper explores three classic clustering problems: $k$-means, $k$-median, and $k$-center. The distinction between these objectives is crucial for determining whether asymptotic exactness is achievable.

Objective functions for k-means, k-median, and k-center clustering problems.

For $k$-means and $k$-median, which involve minimizing a sum of distances, the authors prove that asymptotic exactness is possible provided that the clusters are not "starved" (i.e., the number of points in the smallest cluster $f(n)$ tends to infinity). In these cases, an error of $O(1/\log f(n))$ can be achieved.

In contrast, the $k$-center problem, which minimizes the maximum distance to a center, is shown to be impossible to solve asymptotically exactly in sublinear space. Because the $k$-center objective is determined by a single outlier, the "averaging" effect that allows error to vanish in summation-based objectives does not apply.

Key Results and Impossibility

Beyond clustering, the research highlights a significant divide in the complexity of frequency moments:

  • Frequency Moments: The second moment ($F_2$), which relates to variance, allows for an asymptotically exact algorithm with error $\epsilon = 1/\log n$ using $O(\log^2 n \log(1/\delta))$ memory. Conversely, estimating the number of distinct elements ($F_0$) cannot be made asymptotically exact in sublinear space, despite being "easy" in the standard $(1 \pm \epsilon)$ model.
  • Least Squares Regression: Asymptotic exactness is achievable in the row-arrival model, where the error scales with the smallest singular value of the data matrix. However, in the "turnstile" model (allowing deletions), the problem requires nearly linear space to reach perfect precision.

Conclusion

Asymptotically exact streaming algorithms represent a bridge between traditional streaming theory and statistical limit theorems. By allowing the approximation error to decay as a function of the stream length, these algorithms provide a path toward perfect precision in truly massive datasets. Future work remains to be done in extending this model to graph problems and more complex machine learning estimators.

Summary updated

Abstract

We introduce a new computational model for data streams: asymptotically exact streaming algorithms. These algorithms have an approximation ratio that tends to one as the length of the stream goes to infinity while the memory used by the algorithm is restricted to polylog(n) size. Thus, the output of the algorithm is optimal in the limit. We show positive results in our model for a series of important problems that have been discussed in the streaming literature. These include computing the frequency moments, clustering problems and least squares regression. Our results also include lower bounds for problems, which have streaming algorithms in the ordinary setting but do not allow for sublinear space algorithms in our model.
BibTeX
@misc{heinrich2014asymptotically,
  author = {Marc Heinrich and Alexander Munteanu and Christian Sohler},
  title = {{Asymptotically exact streaming algorithms}},
  year = {2014},
  eprint = {1408.1847},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1408.1847},
}
Figure