A grid-growing clustering algorithm for geo-spatial data

• Propose a grid-based clustering algorithm, which is efficient O(N log  N).
• Take the idea of region growing in image processing into the clustering algorithm.
• Significantly faster than k-means variants, such as litekmeans and PRS, spectral clustering, DBSCAN and Greedy EM.
• The clustering results are comparable to the other clustering algorithms.
• It is very suitable for real geo-spatial data sets.

Geo-spatial data with geographical information explodes as the development of GPS-devices. The data contains certain patterns of users. To dig out the patterns behind the data efficiently, a grid-growing clustering algorithm is introduced. The proposed algorithm takes use of a grid structure, and a novel clustering operation is presented, which considers a grid growing method on the grid structure. The grid structure brings the benefit of efficiency. For large geo-spatial data, the algorithm has competitive strength on the running time. The total time complexity of the algorithm is O(N log  N), where the time complexity mainly comes from the seed selection step. The grid-growing clustering algorithm is useful when the number of clusters is unknown since the algorithm requires no parameter on the number of clusters. The clusters detected could have arbitrary shapes. Furthermore, sparse areas are treated as outliers/noises in the algorithm. An empirical study on several data sets indicates that the proposed algorithm works much more efficiently than other popular clustering algorithms.