Sensitivity Sampling Over Dynamic Geometric Data Streams with Applications to k-Clustering

Zhao Song, Lin F. Yang, Peilin Zhong

Introduction

Clustering is a cornerstone of unsupervised learning, with the $k$-means objective being the most widely utilized variant. As datasets scale to massive proportions, traditional in-memory algorithms become impractical, necessitating the development of streaming models. While "insertion-only" streams—where data only grows—are well-understood, dynamic streams present a significant challenge. In these environments, data points can be both inserted and deleted, requiring algorithms to maintain accurate cluster representations under constant flux.

This paper introduces a breakthrough algorithm for $k$-means clustering in dynamic data streams. It is the first to achieve space complexity that is polynomial in the dimension ($d$) and nearly linear in the number of clusters ($k$), effectively overcoming the "curse of dimensionality" and the sub-optimal scaling of previous approaches.

The Challenge of Dynamic Streams

Previous solutions for dynamic $k$-means typically suffered from one of two major drawbacks. Some were exponential in dimension, making them unsuitable for high-dimensional data common in modern machine learning. Others were sub-optimal in $k$, requiring space proportional to $k^2$ or higher. Given that at least $k$ points are needed to define $k$ clusters, a nearly linear dependency on $k$ is theoretically ideal.

Furthermore, $k$-means is inherently more difficult than $k$-median in a dynamic setting. While $k$-median uses standard Euclidean distance, $k$-means utilizes squared distance. This change prevents the use of standard "telescoping sum" techniques because errors do not scale linearly with grid size, potentially exploding based on the location of cluster centers.

Methodology: Coresets and Sensitivity Sampling

The authors' approach centers on the construction of a "coreset"—a small, weighted subset of the original data that approximates the clustering cost of the full dataset for any set of $k$ centers.

Sensitivity Sampling

To build an effective coreset, the algorithm employs sensitivity sampling. The "sensitivity" of a point measures its importance to the overall clustering cost. A point in an isolated region is highly sensitive because its removal would significantly shift the optimal centers. Conversely, points in dense clusters have low sensitivity. By sampling points with a probability proportional to their sensitivity, the algorithm ensures that outliers and critical cluster boundaries are preserved.

Hierarchical Grids

To estimate sensitivity dynamically, the authors utilize a hierarchy of grids. They track "heavy" cells—those containing a high density of points. A point's sensitivity is bounded based on the smallest grid level where it does not belong to a heavy cell.

As the stream evolves, the algorithm maintains these counts across multiple resolutions. To prevent points from being split awkwardly across grid boundaries, which would distort sensitivity counts, the entire grid system is randomly shifted at initialization.

A finer grid level in the hierarchy, allowing for more precise sensitivity bounds in dense regions.

Implementation Details

The algorithm tracks changes using a specialized "k-set" data structure to monitor heavy cells and their contents. Because the optimal clustering cost ($OPT$) is unknown and fluctuates, the system runs multiple instances in parallel, each testing a different guess for $OPT$ via an exponential search strategy.

Key Results and Impact

The primary contribution is a space-efficient algorithm using $\tilde{O}(k) \cdot \text{poly}(d, \log \Delta, \epsilon^{-1})$ bits of space. This represents a major theoretical milestone, providing the first solution that scales linearly with $k$ while remaining polynomial in $d$ for dynamic streams.

The algorithm processes data in a single pass, making it suitable for high-speed pipelines. With a probability of at least 0.9, it outputs an $\epsilon$-coreset, ensuring that the resulting $k$-means solution is within a $(1+\epsilon)$ factor of the true optimum.

Conclusion

By formalizing the relationship between density and sensitivity and implementing a robust hierarchical grid structure, this work provides a scalable framework for high-dimensional clustering. While future work may focus on reducing the specific polynomial factors of $d$ or extending the model to continuous spaces, this paper sets a new standard for efficiency in dynamic geometric data streams.

Summary updated

Abstract

We consider the $k$-means clustering problem in the dynamic streaming setting, where points from a discrete Euclidean space $\{1, 2, \ldots, \Delta\}^d$ can be dynamically inserted to or deleted from the dataset. For this problem, we provide a one-pass coreset construction algorithm using space $\tilde{O}(k\cdot \mathrm{poly}(d, \log\Delta))$, where $k$ is the target number of centers. To our knowledge, this is the first dynamic geometric data stream algorithm for $k$-means using space polynomial in dimension and nearly optimal (linear) in $k$.
BibTeX
@misc{song2018sensitivity,
  author = {Zhao Song and Lin F. Yang and Peilin Zhong},
  title = {{Sensitivity Sampling Over Dynamic Geometric Data Streams with Applications to k-Clustering}},
  year = {2018},
  eprint = {1802.00459},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.00459},
}
Figure