Nearly Optimal Dynamic $k$-Means Clustering for High-Dimensional Data

Wei Hu, Zhao Song, Lin F. Yang, Peilin Zhong

TL;DR

This paper presents the first algorithm for $k$-means clustering in dynamic data streams (supporting both insertions and deletions) that uses space polynomial in dimension ($d$) and nearly linear in the number of clusters ($k$). By leveraging a novel sensitivity sampling framework based on hierarchical grids, the authors maintain a small "coreset" summary of the data that provides a $(1+\epsilon)$-approximation of the clustering cost.

What Problem Does This Paper Address?

Clustering is a fundamental task in unsupervised learning, with $k$-means being the most widely used variant. However, as datasets grow to massive scales, we often cannot store the entire input. This has led to the development of streaming models, where data points arrive one by one.

The most challenging version of this is the dynamic streaming model, where points can be both inserted and deleted. While algorithms existed for "insertion-only" streams, handling deletions is significantly harder. Previous attempts at dynamic $k$-means either required space that grew exponentially with the dimension ($2^d$), making them useless for high-dimensional data, or were limited to the $k$-median problem.

The $k$-means problem is mathematically more difficult than $k$-median because it uses squared Euclidean distances. This prevents the use of certain "telescoping sum" techniques that rely on the triangle inequality, which works for $k$-median but fails for $k$-means.

Methods

The authors achieve their results by maintaining an $\epsilon$-coreset: a small, weighted subset of the data that behaves almost exactly like the full dataset for any potential set of $k$ cluster centers.

Key Techniques:

  1. Sensitivity Sampling: The core idea is to sample points based on their "sensitivity"—a measure of how much an individual point contributes to the total clustering cost. Points in sparse regions have high sensitivity and must be sampled with higher probability, while points in dense regions can be represented by their neighbors.
  2. Hierarchical Grid Structure: The algorithm partitions the space into a tree of grids. A cell is labeled "heavy" if it contains many points. This structure allows the algorithm to estimate sensitivity: if a point is in a heavy cell, its sensitivity is low.
  3. Random Grid Shifting: To avoid issues where points are split across grid boundaries (which could artificially inflate sensitivity), the entire grid is randomly shifted at the start.
  4. Handling Deletions with $k$-sets: To track points and cell counts in a stream with deletions, the authors use a "sketching" data structure called a $k$-set (or $k$-sparse recovery). This allows them to identify which cells are non-empty and how many points they contain using very little memory.
  5. Exponential Search for OPT: Since the optimal clustering cost (OPT) is unknown and changes as the stream evolves, the algorithm runs multiple instances in parallel, each "guessing" a different value for OPT.

Datasets

This is a theoretical paper focused on algorithmic complexity and provable guarantees. As such, it does not evaluate performance on specific real-world datasets (like MNIST or ImageNet). Instead, it defines the input as points from a discrete Euclidean space $\{1, 2, \ldots, \Delta\}^d$. The results are proven to hold for any distribution of points within this space.

Key Insights and Ideas

  • The $k$-means vs. $k$-median Gap: The authors provide a clear visualization (Figure 3) of why $k$-median techniques fail for $k$-means. In $k$-median, the error of snapping a point to a grid center is bounded linearly by the grid size. In $k$-means, the squared distance causes the error to depend on the location of the cluster centers, potentially exploding the error.
  • Density as a Proxy for Importance: The "aha moment" is that you don't need to know the exact sensitivity of every point. You only need a good upper bound. By identifying "heavy" cells in a hierarchical grid, you can safely assign low sensitivity to points in dense clusters.
  • Space-Efficiency: By combining $k$-sparse recovery sketches with the grid structure, the algorithm avoids the "curse of dimensionality" ($2^d$ space) that plagued previous dynamic geometric algorithms.

Key Results

  • Nearly Optimal Space: The algorithm uses $\tilde{O}(k \cdot \text{poly}(d, \log \Delta, \epsilon^{-1}))$ bits of space. This is the first result to achieve space linear in $k$ for this problem.
  • One-Pass Processing: The algorithm only needs to see each insertion/deletion once.
  • Theoretical Guarantee: With a probability of at least 0.9, the algorithm outputs a weighted set $S$ that is a $(1+\epsilon)$-coreset for the $k$-means objective.
  • Dimension Independence: Unlike previous work, the space complexity is polynomial in $d$, making it suitable for high-dimensional data.

Limitations and Future Work

  • Discrete Space Assumption: The algorithm assumes points come from a discrete grid of size $\Delta$. While $\Delta$ can be very large, extending this to a truly continuous space without any dependence on $\log \Delta$ remains an open challenge.
  • Polynomial Constants: While the space is "polynomial" in $d$, the specific exponents in the proof (e.g., $d^4$ or higher in some sub-routines) might be quite large. Future work could focus on optimizing these constants for practical implementation.
  • Empirical Validation: As a purely theoretical contribution, the paper does not explore how these "sketches" perform against simpler, non-guaranteed heuristics in practice. Testing the robustness of the grid-shifting technique on real-world data distributions would be a logical next step.

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, Δ\}^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Δ))$, 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{hu2018nearly,
  author = {Wei Hu and Zhao Song and Lin F. Yang and Peilin Zhong},
  title = {{Nearly Optimal Dynamic $k$-Means Clustering for High-Dimensional Data}},
  year = {2018},
  eprint = {1802.00459},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.00459},
}
Figure