Best paper award for James Newling at the AI & Statistics International Conference
A Sub-Quadratic Exact Medoid Algorithm
James Newling, Francois Fleuret ;
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:185-193, 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 Rd 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.