Title: Medoids in almost linear time via multi-armed bandits,
Abstract: Computing the medoid of a large number of points in high-dimensional space is
an increasingly common operation in many data science problems. We present an
algorithm Med-dit which uses O(n log n) distance evaluations to compute the
medoid with high probability. Med-dit is based on a connection with the
multi-armed bandit problem. We evaluate the performance of Med-dit empirically
on the Netflix-prize and the single-cell RNA-Seq datasets, containing hundreds
of thousands of points living in tens of thousands of dimensions, and observe a
5-10x improvement in performance over the current state of the art. Med-dit is
available at this https URL