SPANBRE: An Efficient Hierarchical Clustering Algorithm for Spatial Data with Neighborhood Relations

Due to the attributes of the neighbors are always similar or associated to each other, we address the problem of discovering spatial relationships in spatial data through the identification of clusters based on spatial neighborhood relations. We present an efficient clustering algorithm called SPANBRE that generates high quality clusters in O(nlogn) time and in O(n²) message complexity. SPANBRE is kind of agglomerative hierarchical method. By using a sequence data structure, SPANBRE avoids the complex spatial join operation. SPANBRE also execute an optimization strategy for clustering splitting and merging to achieve high clustering quality. The experimental results on traffic flow data sets show that the clustering quality and the algorithm efficiency of SPANBRE are superior to other alternative techniques.