Parallelising the k-medoids clustering problem using space-partitioning

Loading...
Thumbnail Image
Files
SOCS13.pdf(1.57 MB)
Accepted Version
Date
2013
Authors
Arbelaez, Alejandro
Quesada, Luis
Journal Title
Journal ISSN
Volume Title
Publisher
Association for the Advancement of Artificial Intelligence
Research Projects
Organizational Units
Journal Issue
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.
Description
Keywords
Local search , Parallel search , k-medoids , Clustering
Citation
Arbelaez, A. and Quesada, L. (2013) 'Parallelising the k-medoids clustering problem using space-partitioning', Proceedings of the International Symposium on Combinatorial Search 4(1), pp. 20-28. doi: https://doi.org/10.1609/socs.v4i1.18282
Copyright
© 2013, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.