Density-based clustering techniques are used in a wide range of data mining applications. One of their most attractive features con- sists in not making use of prior knowledge of the number of clusters that a dataset contains along with their shape. In this paper we propose a new algorithm named Linear DBSCAN (Lin-DBSCAN), a simple approach to clustering inspired by the density model introduced with the well known algorithm DBSCAN. Designed to minimize the computational cost of density based clustering on geospatial data, Lin-DBSCAN features a linear time complexity that makes it suitable for real-time applications on low-resource devices. Lin-DBSCAN uses a discrete version of the density model of DBSCAN that takes ad- vantage of a grid-based scan and merge approach. The name of the algorithm stems exactly from its main features outlined above. The algorithm was tested with well known data sets. Experimental results prove the efficiency and the validity of this approach over DBSCAN in the context of spatial data clustering, enabling the use of a density-based clustering technique on large datasets with low computational cost.
Spatial data clustering is one of the important data mining techniques for extracting knowledge from large amount of spatial data collected in various applications, such as remote sensing, GIS, computer cartography, environmental assessment and planning, etc. Several useful and popular spatial data clustering algorithms have been proposed in the past decade. DBSCAN is one of them, which can discover clusters of any arbitrary shape and can handle the noise points effectively. However, DBSCAN requires large volume of memory support because it operates on the entire database. This paper presents an improved sampling-based DBSCAN which can cluster large-scale spatial databases effectively. Experimental results included to establish that the proposed sampling-based DBSCAN outperforms DBSCAN as well as its other counterparts, in terms of execution time, without losing the quality of clustering. DBSCAN is a typical clustering algorithm, which can discover clusters with any arbitrary shape and handle noise well. However, it is also slow in comparison due to neighborhood query for each object and faces difficulty in setting density threshold properly. In this paper, a fast density-based clustering algorithm is presented based on DBSCAN. After sorting objects by a certain dimensional coordinates, the new algorithm selects orderly unlabelled points outside a core object's neighborhood as seeds to expand clusters so that the execution frequency of region queries can be decreased. Objects are transformed with a kernel function to improve the clustering accuracy, which diminishes the dependency of density threshold to some extent. Theoretic analysis indicates that the time complexity of this algorithm is approximately linear. Experiments show that the efficiency and the quality for clusters of the proposed algorithm are remarkably superior to those of DBSCAN.