# A Sub-Quadratic Exact Medoid Algorithm

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2016.

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

- [Discrepancy-Based Active Learning for Domain Adaptation](https://mlsanity.com/paper/2103.03757/) (2021)
- [Machine Learning Approach to Uncovering Residential Energy Consumption Patterns Based on Socioeconomic and Smart Meter Data](https://mlsanity.com/paper/2104.05154/) (2021)
- [Metric-valued regression](https://mlsanity.com/paper/2202.03045/) (2022)
- [Data Aggregation for Hierarchical Clustering](https://mlsanity.com/paper/2309.02552/) (2023)
- [Implications of Distance over Redistricting Maps: Central and Outlier Maps](https://mlsanity.com/paper/2203.00872/) (2022)
- [Sparse Partitioning Around Medoids](https://mlsanity.com/paper/2309.02557/) (2023)

## Abstract (arXiv)

We present a new algorithm, trimed, for obtaining the medoid of a set, that is the element of the set which minimises the mean distance to all other elements. The algorithm is shown to have, under certain assumptions, expected run time O(N^(3/2)) in R^d where N is the set size, making it the first sub-quadratic exact medoid algorithm for d>1. Experiments show that it performs very well on spatial network data, frequently requiring two orders of magnitude fewer distance calculations than state-of-the-art approximate algorithms. As an application, we show how trimed can be used as a component in an accelerated K-medoids algorithm, and then how it can be relaxed to obtain further computational gains with only a minor loss in cluster quality.