# BanditPAM++: Faster k-medoids Clustering

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 27 references that are in the map.
- First posted on arXiv 28 Oct 2023.

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

- [Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms](https://mlsanity.com/paper/1810.05691/) (2018)
- [Medoids in almost linear time via multi-armed bandits](https://mlsanity.com/paper/1711.00817/) (2017)
- [Active Distance-Based Clustering using K-medoids](https://mlsanity.com/paper/1512.03953/) (2015)
- [Adaptive Estimation for Approximate k-Nearest-Neighbor Computations](https://mlsanity.com/paper/1902.09465/) (2019)
- [MABSplit: Faster Forest Training Using Multi-Armed Bandits](https://mlsanity.com/paper/2212.07473/) (2022)
- [Accelerating Machine Learning Algorithms with Adaptive Sampling](https://mlsanity.com/paper/2309.14221/) (2023)

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

- [Addressing the Cold-Start Problem for Personalized Combination Drug Screening](https://mlsanity.com/paper/2509.07850/) (2025)
- [A Scalable k-Medoids Clustering via Whale Optimization Algorithm](https://mlsanity.com/paper/2408.16993/) (2024)

## Abstract (arXiv)

Clustering is a fundamental task in data science with wide-ranging applications. In k-medoids clustering, cluster centers must be actual datapoints and arbitrary distance metrics may be used; these features allow for greater interpretability of the cluster centers and the clustering of exotic objects in k-medoids clustering, respectively. k-medoids clustering has recently grown in popularity due to the discovery of more efficient k-medoids algorithms. In particular, recent research has proposed BanditPAM, a randomized k-medoids algorithm with state-of-the-art complexity and clustering accuracy. In this paper, we present BanditPAM++, which accelerates BanditPAM via two algorithmic improvements, and is O(k) faster than BanditPAM in complexity and substantially faster than BanditPAM in wall-clock runtime. First, we demonstrate that BanditPAM has a special structure that allows the reuse of clustering information textitwithin each iteration. Second, we demonstrate that BanditPAM has additional structure that permits the reuse of information textitacross different iterations. These observations inspire our proposed algorithm, BanditPAM++, which returns the same clustering solutions as BanditPAM but often several times faster. For example, on the CIFAR10 dataset, BanditPAM++ returns the same results as BanditPAM but runs over 10× faster. Finally, we provide a high-performance C++ implementation of BanditPAM++, callable from Python and R, that may be of interest to practitioners at https://github.com/motiwari/BanditPAM. Auxiliary code to reproduce all of our experiments via a one-line script is available at https://github.com/ThrunGroup/BanditPAMplusplusexperiments.