# Fast and Eager k-Medoids Clustering: O(k) Runtime Improvement of the PAM, CLARA, and CLARANS Algorithms

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Aug 2020.

## Built on by (most cited first, 30 of 36)

- [Stop using the elbow criterion for k-means and how to choose the number of clusters instead](https://mlsanity.com/paper/2212.12189/) (2022)
- [Generalized Coverage for More Robust Low-Budget Active Learning](https://mlsanity.com/paper/2407.12212/) (2024)
- [Uncertainty Herding: One Active Learning Method for All Label Budgets](https://mlsanity.com/paper/2412.20644/) (2024)
- [A Rapid Review of Clustering Algorithms](https://mlsanity.com/paper/2401.07389/) (2024)
- [Intelligent sampling for surrogate modeling, hyperparameter optimization, and data analysis](https://mlsanity.com/paper/2306.04066/) (2023)
- [Medoid Silhouette clustering with automatic cluster number selection](https://mlsanity.com/paper/2309.03751/) (2023)
- [Clustering by Direct Optimization of the Medoid Silhouette](https://mlsanity.com/paper/2209.12553/) (2022)
- [Random Forest Autoencoders for Guided Representation Learning](https://mlsanity.com/paper/2502.13257/) (2025)
- [A review of clustering models in educational data science towards fairness-aware learning](https://mlsanity.com/paper/2301.03421/) (2023)
- [No Pattern, No Recognition: a Survey about Reproducibility and Distortion Issues of Text Clustering and Topic Modeling](https://mlsanity.com/paper/2208.01712/) (2022)
- [UniForCE: The Unimodality Forest Method for Clustering and Estimation of the Number of Clusters](https://mlsanity.com/paper/2312.11323/) (2023)
- [Investigating Writing Professionals' Relationships with Generative AI: How Combined Perceptions of Rivalry and Collaboration Shape Work Practices and Outcomes](https://mlsanity.com/paper/2602.08227/) (2026)
- [Socially Fair Center-based and Linear Subspace Clustering](https://mlsanity.com/paper/2208.10095/) (2022)
- [Min-Max-Jump distance and its applications](https://mlsanity.com/paper/2301.05994/) (2023)
- [Data Aggregation for Hierarchical Clustering](https://mlsanity.com/paper/2309.02552/) (2023)
- [Mitigating Pilot Contamination and Enabling IoT Scalability in Massive MIMO Systems](https://mlsanity.com/paper/2310.03278/) (2023)
- [EKM: An exact, polynomial-time algorithm for the K-medoids problem](https://mlsanity.com/paper/2405.12237/) (2024)
- [Interactive Counterfactual Exploration of Algorithmic Harms in Recommender Systems](https://mlsanity.com/paper/2409.06916/) (2024)
- [Diverse Mini-Batch Selection in Reinforcement Learning for Efficient Chemical Exploration in de novo Drug Design](https://mlsanity.com/paper/2506.21158/) (2025)
- [Density-Aware Farthest Point Sampling](https://mlsanity.com/paper/2509.13213/) (2025)
- [Atlas-based Manifold Representations for Interpretable Riemannian Machine Learning](https://mlsanity.com/paper/2510.17772/) (2025)
- [In-Context Learning for the Imputation of Public Opinion Data with Large Language Models](https://mlsanity.com/paper/2606.09351/) (2026)
- [ATLAS: Scaffold-Free Algorithm Synthesis by LLMs via Embedding-Guided Quality-Diversity Search](https://mlsanity.com/paper/2608.15546/) (2026)
- [K-Means for Noise-Insensitive Multi-Dimensional Feature Learning](https://mlsanity.com/paper/2202.07754/) (2022)
- [Sparse Partitioning Around Medoids](https://mlsanity.com/paper/2309.02557/) (2023)
- [Re-localization acceleration with Medoid Silhouette Clustering](https://mlsanity.com/paper/2407.20749/) (2024)
- [Forest-Guided Clustering -- Shedding Light into the Random Forest Black Box](https://mlsanity.com/paper/2507.19455/) (2025)
- [Dimensionally Reduced Open-World Clustering: DROWCULA](https://mlsanity.com/paper/2509.07184/) (2025)
- [Effectiveness of High-Dimensional Distance Metrics on Solar Flare Time Series](https://mlsanity.com/paper/2511.01873/) (2025)
- [CSMapping: Scalable Crowdsourced Semantic Mapping and Topology Inference for Autonomous Driving](https://mlsanity.com/paper/2512.03510/) (2025)

## Abstract (arXiv)

Clustering non-Euclidean data is difficult, and one of the most used algorithms besides hierarchical clustering is the popular algorithm Partitioning Around Medoids (PAM), also simply referred to as k-medoids clustering. In Euclidean geometry the mean-as used in k-means-is a good estimator for the cluster center, but this does not exist for arbitrary dissimilarities. PAM uses the medoid instead, the object with the smallest dissimilarity to all others in the cluster. This notion of centrality can be used with any (dis-)similarity, and thus is of high relevance to many domains and applications. A key issue with PAM is its high run time cost. We propose modifications to the PAM algorithm that achieve an O(k)-fold speedup in the second ("SWAP") phase of the algorithm, but will still find the same results as the original PAM algorithm. If we relax the choice of swaps performed (while retaining comparable quality), we can further accelerate the algorithm by eagerly performing additional swaps in each iteration. With the substantially faster SWAP, we can now explore faster initialization strategies, because (i) the classic ("BUILD") initialization now becomes the bottleneck, and (ii) our swap is fast enough to compensate for worse starting conditions. We also show how the CLARA and CLARANS algorithms benefit from the proposed modifications. While we do not study the parallelization of our approach in this work, it can easily be combined with earlier approaches to use PAM and CLARA on big data (some of which use PAM as a subroutine, hence can immediately benefit from these improvements), where the performance with high k becomes increasingly important. In experiments on real data with k=100,200, we observed a 458x respectively 1191x speedup compared to the original PAM SWAP algorithm, making PAM applicable to larger data sets, and in particular to higher k.