# OneBatchPAM: A Fast and Frugal K-Medoids Algorithm

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jan 2025.

## 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)
- [ScreenShot: A Foundation Model for Few-Shot Combination Drug Screening](https://mlsanity.com/paper/2608.12219/) (2026)

## Abstract (arXiv)

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.