# Medoids in almost linear time via multi-armed bandits

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2017.

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

- [Hyperparameter-Free Approach for Faster Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2401.02749/) (2024)
- [Batch Active Learning of Reward Functions from Human Preferences](https://mlsanity.com/paper/2402.15757/) (2024)
- [Asymptotic Theory of Geometric and Adaptive k-Means Clustering](https://mlsanity.com/paper/2202.13423/) (2022)
- [Approximate Function Evaluation via Multi-Armed Bandits](https://mlsanity.com/paper/2203.10124/) (2022)
- [MABSplit: Faster Forest Training Using Multi-Armed Bandits](https://mlsanity.com/paper/2212.07473/) (2022)
- [Incremental Extractive Opinion Summarization Using Cover Trees](https://mlsanity.com/paper/2401.08047/) (2024)
- [Faster Maximum Inner Product Search in High Dimensions](https://mlsanity.com/paper/2212.07551/) (2022)
- [BanditPAM++: Faster k-medoids Clustering](https://mlsanity.com/paper/2310.18844/) (2023)
- [Adaptive Data Depth via Multi-Armed Bandits](https://mlsanity.com/paper/2211.03985/) (2022)
- [Nearest Neighbor Search Under Uncertainty](https://mlsanity.com/paper/2103.05057/) (2021)

## Abstract (arXiv)

Computing the medoid of a large number of points in high-dimensional space is an increasingly common operation in many data science problems. We present an algorithm Med-dit which uses O(n log n) distance evaluations to compute the medoid with high probability. Med-dit is based on a connection with the multi-armed bandit problem. We evaluate the performance of Med-dit empirically on the Netflix-prize and the single-cell RNA-Seq datasets, containing hundreds of thousands of points living in tens of thousands of dimensions, and observe a 5-10x improvement in performance over the current state of the art. Med-dit is available at https://github.com/bagavi/Meddit