# Incremental Clustering: The Case for Extra Clusters

arXiv: https://arxiv.org/abs/1406.6398 · HTML: https://mlsanity.com/paper/1406.6398/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2014.

## Built on by (most cited first, 5 of 5)

- [Prototypical Fine-tuning: Towards Robust Performance Under Varying Data Sizes](https://mlsanity.com/paper/2211.13638/) (2022)
- [Graceful Forgetting II. Data as a Process](https://mlsanity.com/paper/2211.15441/) (2022)
- [Are Easy Data Easy (for K-Means)](https://mlsanity.com/paper/2308.01926/) (2023)
- [Graceful forgetting: Memory as a process](https://mlsanity.com/paper/2502.11105/) (2025)
- [Hierarchical Linkage Clustering Beyond Binary Trees and Ultrametrics](https://mlsanity.com/paper/2511.18056/) (2025)

## Abstract (arXiv)

The explosion in the amount of data available for analysis often necessitates a transition from batch to incremental clustering methods, which process one element at a time and typically store only a small subset of the data. In this paper, we initiate the formal analysis of incremental clustering methods focusing on the types of cluster structure that they are able to detect. We find that the incremental setting is strictly weaker than the batch model, proving that a fundamental class of cluster structures that can readily be detected in the batch setting is impossible to identify using any incremental method. Furthermore, we show how the limitations of incremental clustering can be overcome by allowing additional clusters.