AAAI Publications, Sixth Annual Symposium on Combinatorial Search

Font Size: 
Parallelising the k-Medoids Clustering Problem Using Space-Partitioning
Alejandro Arbelaez, Luis Quesada

Last modified: 2013-06-19


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.

Full Text: PDF