# Ultra Fast Medoid Identification via Correlated Sequential Halving

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2019.

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

- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [Hyperparameter-Free Approach for Faster Minimum Bayes Risk Decoding](https://mlsanity.com/paper/2401.02749/) (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)
- [Metric-valued regression](https://mlsanity.com/paper/2202.03045/) (2022)
- [Faster Maximum Inner Product Search in High Dimensions](https://mlsanity.com/paper/2212.07551/) (2022)
- [Adaptive Data Depth via Multi-Armed Bandits](https://mlsanity.com/paper/2211.03985/) (2022)

## Abstract (arXiv)

The medoid of a set of n points is the point in the set that minimizes the sum of distances to other points. It can be determined exactly in O(n^2) time by computing the distances between all pairs of points. Previous works show that one can significantly reduce the number of distance computations needed by adaptively querying distances. The resulting randomized algorithm is obtained by a direct conversion of the computation problem to a multi-armed bandit statistical inference problem. In this work, we show that we can better exploit the structure of the underlying computation problem by modifying the traditional bandit sampling strategy and using it in conjunction with a suitably chosen multi-armed bandit algorithm. Four to five orders of magnitude gains over exact computation are obtained on real data, in terms of both number of distance computations needed and wall clock time. Theoretical results are obtained to quantify such gains in terms of data parameters. Our code is publicly available online at https://github.com/TavorB/Correlated-Sequential-Halving.