Parallelising the k-Medoids Clustering Problem Using Space-Partitioning

Authors

  • Alejandro Arbelaez JFLI / University of Tokyo
  • Luis Quesada University College Cork

DOI:

https://doi.org/10.1609/socs.v4i1.18282

Keywords:

Local Search, Parallel Search, k-Medoids, Clustering

Abstract

The k-medoids problem is a combinatorial optimisation problem with multiples applications in Resource Allocation, Mobile Computing, Sensor Networks and Telecommunications.Real instances of this problem involve hundreds of thousands of points and thousands of medoids.Despite the proliferation of parallel architectures, this problem has been mostly tackled using sequential approaches.In this paper, we study the impact of space-partitioning techniques on the performance of parallel local search algorithms to tackle the k-medoids clustering problem, and compare these results with the ones obtained using sampling.Our experiments suggest that approaches relying on partitioning scale more while preserving the quality of the solution.

Downloads

Published

2021-08-20