Data clustering algorithm based on digital search tree

Clustering is an important data analyzing method in data mining. In this paper, we analyzed existing clustering algorithms and raised a new density-based grid clustering algorithm based on digital search tree (DST). We classified DST as a new kind of clustering method and gave out the construction algorithm of the region-density digital search tree (RD-DST) and its clustering algorithm. We then extended the algorithm to high-dimensional data space and analyzed the space and time complexities of the RD-DST based clustering algorithm. We further proved that the RD-DST based clustering algorithm only did grid division of the non-empty space in the high-dimensional data space. It lowers the number of the grid unit drastically and gain higher space and time efficiency.