%Aigaion2 BibTeX export from Idiap Publications
%Friday 05 December 2025 01:12:51 PM

@TECHREPORT{Newling_Idiap-RR-19-2017,
                      author = {Newling, James and Fleuret, Francois},
                    keywords = {clustering, exact, k-medoids, medoid, scalable, sub-quadratic},
                    projects = {Idiap},
                       month = {7},
                       title = {A Sub-Quadratic Exact Medoid Algorithm},
                        type = {Idiap-RR},
                      number = {Idiap-RR-19-2017},
                        year = {2017},
                 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.},
                         pdf = {https://publications.idiap.ch/attachments/reports/2016/Newling_Idiap-RR-19-2017.pdf}
}