IMPROVED BISECTOR CLUSTERING OF UNCERTAIN DATA USING SDSA METHOD ON PARALLEL PROCESSORS

Clustering uncertain objects is a well researched field. This paper is concerned with clustering uncertain objects with 2D location uncertainty due to object movements. Location of moving object is reported periodically, thus location is uncertain and described with probability density function (PDF). Data about moving objects and their locations are placed in distributed databases. Number of uncertain objects can be very large and obtaining quality result within reasonable time is a challenging task. Basic clustering method is UK-means, in which all expected distances (ED) from objects to clusters are calculated. Thus UK-means is inefficient. To avoid ED calculations various pruning methods are proposed. A survey of existing clustering methods is given in this paper and a combination of two methods is proposed. The first method, called Segmentation of Data Set Area is combined with Improved Bisector pruning to improve execution time of clustering uncertain data. In SDSA method, data set area is divided in many small segments, and only objects in that small segment are observed. Using segments there is a possibility for parallel computing, because segments are mutually independent, thus each segment can be computed on different core of parallel processor. Experiments were conducted to evaluate the effectiveness of the combined methods.