A SubQuadratic Exact Medoid Algorithm
[edit]
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:185193, 2017.
Abstract
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 subquadratic 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 stateoftheart approximate algorithms. As an application, we show how trimed can be used as a component in an accelerated Kmedoids algorithm, and then how it can be relaxed to obtain further computational gains with only a minor loss in cluster quality.
Related Material


