Author(s)

C.-S. Chiang, S.-C. Chu, J. F. Chang & J.-S. Pan

Abstract

In this paper, a new inequality is derived which can be used for the problem of nearest neighbor searching. We also present a searching technique referred to as a previous medoid index to reduce the computation time particularly for the kmedoids- based algorithms. A novel method is also proposed to reduce the computational complexity by the utilization of memory. Four new search strategies for k-medoids-based algorithms based on the new inequality, previous medoid index, the utilization of memory, triangular inequality criteria and partial distance search are proposed. Experimental results demonstrate that the proposed algorithm applied to the CLARANS algorithm may reduce the computation time from 88.8% to 95.3% with the same average distance per object comparing with CLALRANS. The derived new inequality and proposed search strategies can also be applied to the nearest neighbor searching and the other clustering algorithms. 1 Introduction The goal of clustering , in general, is to group sets of objects into classes such that homogeneous objects are placed in the same cluster while dissimilar objects are in separate clusters. Clustering (or classification) techniques are common forms

Keywords