logo Idiap Research Institute        
 [BibTeX] [Marc21]
A Sub-Quadratic Exact Medoid Algorithm
Type of publication: Idiap-RR
Citation: Newling_Idiap-RR-19-2017
Number: Idiap-RR-19-2017
Year: 2017
Month: 7
Institution: Idiap
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 weak assumptions, complexity 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 distances than state-of-the-art approximate algorithms. We show how trimed can be used as a component in an accelerated K-medoids algorithm, and how it can be relaxed to obtain further computational gains with an only minor loss in quality.
Keywords: clustering, exact, k-medoids, medoid, scalable, sub-quadratic
Projects Idiap
Authors Newling, James
Fleuret, Francois
Added by: [ADM]
Total mark: 0
  • Newling_Idiap-RR-19-2017.pdf (MD5: bc4a48cad6ee6d805e17a8c0d7b61b7e)