QuickDBC: uma separação rápida de clusters baseada em densidade para espaços métricos

Abstract

The class identification task for spatial databases can be achieved by clustering algorithms. However, it requires a domain knowledge to determine some input parameters to discover clusters and the improvement of its efficiency on large databases remains a challenge. Modern applications also deal with complex data and the comparison mechanisms are based on similarity predicates, which demands a new front of clustering algorithms. Complex data are usually immersed in metric spaces where distance functions are employed to express the similarity. Clustering becomes a difficult task due to the need of performing distance calculations. Density-based are one of the most interesting approaches to find clusters in metric spaces and have the advantage of finding clusters without the need of specifying the number of clusters to find. Although some suggested using indexes to speed up neighbor queries, they still process the entire space of elements calculating distances before finding clusters. In this paper we propose a new technique to separate clusters by using pivots selected at the border of the data space. Multiple pivots partition the data space into candidate clusters based on the desired density level, later all candidates are fused generating a good separation of clusters. Our technique can also be used prior to any existing clustering technique for a performance speed up. Therefore, we performed experiments by using one density clustering algorithm from literature and the results showed that our technique reduced the cost of the clustering process.