OneBatchPAM: A Fast and Frugal K-Medoids Algorithm
Antoine de Mathelin, Nicolas Enrique Cecchi, François Deheeger, Mathilde Mougeot, Nicolas Vayatis
Abstract
This paper proposes a novel k-medoids approximation algorithm to handle large-scale datasets with reasonable computational time and memory complexity. We develop a local-search algorithm that iteratively improves the medoid selection based on the estimation of the k-medoids objective. A single batch of size m << n provides the estimation, which reduces the required memory size and the number of pairwise dissimilarities computations to O(mn), instead of O(n^2) compared to most k-medoids baselines. We obtain theoretical results highlighting that a batch of size m = O(log(n)) is sufficient to guarantee, with strong probability, the same performance as the original local-search algorithm. Multiple experiments conducted on real datasets of various sizes and dimensions show that our algorithm provides similar performances as state-of-the-art methods such as FasterPAM and BanditPAM++ with a drastically reduced running time.
BibTeX
@article{de Mathelin_Cecchi_Deheeger_Mougeot_Vayatis_2025, title={OneBatchPAM: A Fast and Frugal K-Medoids Algorithm}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/33776}, DOI={10.1609/aaai.v39i15.33776}, abstractNote={This paper proposes a novel k-medoids approximation algorithm to handle large-scale datasets with reasonable computational time and memory complexity. We develop a local-search algorithm that iteratively improves the medoid selection based on the estimation of the k-medoids objective. A single batch of size m << n provides the estimation, which reduces the required memory size and the number of pairwise dissimilarities computations to O(mn), instead of O(n^2) compared to most k-medoids baselines. We obtain theoretical results highlighting that a batch of size m = O(log(n)) is sufficient to guarantee, with strong probability, the same performance as the original local-search algorithm. Multiple experiments conducted on real datasets of various sizes and dimensions show that our algorithm provides similar performances as state-of-the-art methods such as FasterPAM and BanditPAM++ with a drastically reduced running time.}, number={15}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={de Mathelin, Antoine and Cecchi, Nicolas Enrique and Deheeger, François and Mougeot, Mathilde and Vayatis, Nicolas}, year={2025}, month={Apr.}, pages={16172-16180} }