Medoids in almost linear time via multi-armed bandits

November 02, 2017 · Entered Twilight · 🏛 International Conference on Artificial Intelligence and Statistics

"Last commit was 8.0 years ago (≥5 year threshold)"

Evidence collected by the PWNC Scanner

Repo contents: .gitignore, README.md, datasets, experiments, figure, file_struture, scripts

Authors Vivek Bagaria, Govinda M. Kamath, Vasilis Ntranos, Martin J. Zhang, David Tse arXiv ID 1711.00817 Category stat.ML: Machine Learning (Stat) Cross-listed cs.DS, cs.IT, cs.LG Citations 36 Venue International Conference on Artificial Intelligence and Statistics Repository https://github.com/bagavi/Meddit ⭐ 8 Last Checked 1 month ago

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 https://github.com/bagavi/Meddit