# Active Distance-Based Clustering using K-medoids

arXiv: https://arxiv.org/abs/1512.03953 · HTML: https://mlsanity.com/paper/1512.03953/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2015.

## Built on by (most cited first, 8 of 8)

- [Generalized Coverage for More Robust Low-Budget Active Learning](https://mlsanity.com/paper/2407.12212/) (2024)
- [Uncertainty Herding: One Active Learning Method for All Label Budgets](https://mlsanity.com/paper/2412.20644/) (2024)
- [Approximately Optimal Core Shapes for Tensor Decompositions](https://mlsanity.com/paper/2302.03886/) (2023)
- [Active Learning with a Noisy Annotator](https://mlsanity.com/paper/2504.04506/) (2025)
- [BanditPAM++: Faster k-medoids Clustering](https://mlsanity.com/paper/2310.18844/) (2023)
- [To Label or Not to Label: PALM -- A Predictive Model for Evaluating Sample Efficiency in Active Learning Models](https://mlsanity.com/paper/2507.15381/) (2025)
- [Exploring Active Learning in Meta-Learning: Enhancing Context Set Labeling](https://mlsanity.com/paper/2311.02879/) (2023)
- [A Mechanism-Driven Theory of Phase Transitions in Active Learning](https://mlsanity.com/paper/2607.00144/) (2026)

## Abstract (arXiv)

k-medoids algorithm is a partitional, centroid-based clustering algorithm which uses pairwise distances of data points and tries to directly decompose the dataset with n points into a set of k disjoint clusters. However, k-medoids itself requires all distances between data points that are not so easy to get in many applications. In this paper, we introduce a new method which requires only a small proportion of the whole set of distances and makes an effort to estimate an upper-bound for unknown distances using the inquired ones. This algorithm makes use of the triangle inequality to calculate an upper-bound estimation of the unknown distances. Our method is built upon a recursive approach to cluster objects and to choose some points actively from each bunch of data and acquire the distances between these prominent points from oracle. Experimental results show that the proposed method using only a small subset of the distances can find proper clustering on many real-world and synthetic datasets.