# SECLEDS: Sequence Clustering in Evolving Data Streams via Multiple Medoids and Medoid Voting

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 33 references that are in the map.
- First posted on arXiv 24 Jun 2022.

## Builds on (most cited first, 6 of 6)

- [Learning under Concept Drift: A Review](https://mlsanity.com/paper/2004.05785/) (2020)
- [Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms](https://mlsanity.com/paper/1810.05691/) (2018)
- [Data Stream Clustering: A Review](https://mlsanity.com/paper/2007.10781/) (2020)
- [Time series clustering based on the characterisation of segment typologies](https://mlsanity.com/paper/1810.11624/) (2018)
- [K-medoids Clustering of Data Sequences with Composite Distributions](https://mlsanity.com/paper/1807.11620/) (2018)
- [BanditPAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits](https://mlsanity.com/paper/2006.06856/) (2020)

## Abstract (arXiv)

Sequence clustering in a streaming environment is challenging because it is computationally expensive, and the sequences may evolve over time. K-medoids or Partitioning Around Medoids (PAM) is commonly used to cluster sequences since it supports alignment-based distances, and the k-centers being actual data items helps with cluster interpretability. However, offline k-medoids has no support for concept drift, while also being prohibitively expensive for clustering data streams. We therefore propose SECLEDS, a streaming variant of the k-medoids algorithm with constant memory footprint. SECLEDS has two unique properties: i) it uses multiple medoids per cluster, producing stable high-quality clusters, and ii) it handles concept drift using an intuitive Medoid Voting scheme for approximating cluster distances. Unlike existing adaptive algorithms that create new clusters for new concepts, SECLEDS follows a fundamentally different approach, where the clusters themselves evolve with an evolving stream. Using real and synthetic datasets, we empirically demonstrate that SECLEDS produces high-quality clusters regardless of drift, stream size, data dimensionality, and number of clusters. We compare against three popular stream and batch clustering algorithms. The state-of-the-art BanditPAM is used as an offline benchmark. SECLEDS achieves comparable F1 score to BanditPAM while reducing the number of required distance computations by 83.7%. Importantly, SECLEDS outperforms all baselines by 138.7% when the stream contains drift. We also cluster real network traffic, and provide evidence that SECLEDS can support network bandwidths of up to 1.08 Gbps while using the (expensive) dynamic time warping distance.