Linear density-based clustering with a discrete density model
  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.
