A Sub-Quadratic Exact Medoid Algorithm
This provides a faster exact solution for medoid computation, which is useful in clustering and data analysis applications, though it is incremental as it builds on existing medoid algorithms.
The authors tackled the problem of efficiently computing the exact medoid of a set, which minimizes the mean distance to other elements, by introducing a new algorithm called trimed that achieves expected run time O(N^(3/2)) in R^d, making it the first sub-quadratic exact method for d>1, and experiments show it reduces distance calculations by up to two orders of magnitude compared to state-of-the-art approximate algorithms.
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.