# Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms

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

## Key facts

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

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

- [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)
- [Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond](https://mlsanity.com/paper/2402.17327/) (2024)
- [Uncertainty Herding: One Active Learning Method for All Label Budgets](https://mlsanity.com/paper/2412.20644/) (2024)
- [SPOT: A framework for selection of prototypes using optimal transport](https://mlsanity.com/paper/2103.10159/) (2021)
- [Agglomerative Token Clustering](https://mlsanity.com/paper/2409.11923/) (2024)
- [Regist3R: Incremental Registration with Stereo Foundation Model](https://mlsanity.com/paper/2504.12356/) (2025)
- [Transferring Experience from Simulation to the Real World for Precise Pick-And-Place Tasks in Highly Cluttered Scenes](https://mlsanity.com/paper/2101.04781/) (2021)
- [CARL-G: Clustering-Accelerated Representation Learning on Graphs](https://mlsanity.com/paper/2306.06936/) (2023)
- [Medoid Silhouette clustering with automatic cluster number selection](https://mlsanity.com/paper/2309.03751/) (2023)
- [Learning Interpretable Queries for Explainable Image Classification with Information Pursuit](https://mlsanity.com/paper/2312.11548/) (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)
- [Tackling Provably Hard Representative Selection via Graph Neural Networks](https://mlsanity.com/paper/2205.10403/) (2022)
- [Memory Classifiers: Two-stage Classification for Robustness in Machine Learning](https://mlsanity.com/paper/2206.05323/) (2022)
- [No Pattern, No Recognition: a Survey about Reproducibility and Distortion Issues of Text Clustering and Topic Modeling](https://mlsanity.com/paper/2208.01712/) (2022)
- [Simple, Scalable and Effective Clustering via One-Dimensional Projections](https://mlsanity.com/paper/2310.16752/) (2023)
- [BanditPAM++: Faster k-medoids Clustering](https://mlsanity.com/paper/2310.18844/) (2023)
- [Flexible ViG: Learning the Self-Saliency for Flexible Object Recognition](https://mlsanity.com/paper/2406.18585/) (2024)
- [Navigating Trade-offs: Policy Summarization for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2411.04784/) (2024)
- [SynQuE: Estimating Synthetic Dataset Quality Without Annotations](https://mlsanity.com/paper/2511.03928/) (2025)
- [Data augmentation and feature selection for automatic model recommendation in computational physics](https://mlsanity.com/paper/2101.04530/) (2021)
- [Bayesian nonparametric mixture inconsistency for the number of components: How worried should we be in practice?](https://mlsanity.com/paper/2207.14717/) (2022)
- [Generating Multidimensional Clusters With Support Lines](https://mlsanity.com/paper/2301.10327/) (2023)
- [Data Aggregation for Hierarchical Clustering](https://mlsanity.com/paper/2309.02552/) (2023)
- [An algorithm for forensic toolmark comparisons](https://mlsanity.com/paper/2312.00032/) (2023)
- [Automating Weak Label Generation for Data Programming with Clinicians in the Loop](https://mlsanity.com/paper/2407.07982/) (2024)
- [A multi-criteria decision support system to evaluate the effectiveness of training courses on citizens' employability](https://mlsanity.com/paper/2412.01351/) (2024)
- [Diverse Mini-Batch Selection in Reinforcement Learning for Efficient Chemical Exploration in de novo Drug Design](https://mlsanity.com/paper/2506.21158/) (2025)
- [Addressing the Cold-Start Problem for Personalized Combination Drug Screening](https://mlsanity.com/paper/2509.07850/) (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. In Euclidean geometry the mean-as used in k-means-is a good estimator for the cluster center, but this does not hold 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 such as biology that require the use of Jaccard, Gower, or more complex distances. A key issue with PAM is its high run time cost. We propose modifications to the PAM algorithm to 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 slightly relax the choice of swaps performed (at comparable quality), we can further accelerate the algorithm by performing up to k swaps in each iteration. With the substantially faster SWAP, we can now also explore alternative strategies for choosing the initial medoids. We also show how the CLARA and CLARANS algorithms benefit from these modifications. 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, we observed a 200-fold speedup compared to the original PAM SWAP algorithm, making PAM applicable to larger data sets as long as we can afford to compute a distance matrix, and in particular to higher k (at k=2, the new SWAP was only 1.5 times faster, as the speedup is expected to increase with k).