Abstract:This paper presents a research on speeding up K-medoids clustering algorithm. Firstly, two acceleration lemmas are given based on partitioning around medoids(PAM) and triangular inequality elimination criteria PAM(TPAM) algorithms. Then two new acceleration theorems are proposed based on distance inequality between center points. Combining the lemmas with the theorems with the aid of additional memory space O(n+K2), the speed up partitioning around medoids(SPAM) algorithm is constructed, reducing the time complexity from O(K(n-K)2) to O((n-K)2). Experimental results on both real-world and artificial datasets show that the SPAM algorithm outperforms PAM, TPAM and FKEMDOIDS approaches by at least 0.828 times over PAM in terms of running time.