Abstract:To tackle the problem that density-based spatial clustering of applications with noise (DBSCAN) clustering algorithm is increasingly time-consuming with the increase in data volume, this study proposes an improved DBSCAN algorithm based on a K-dimensional (KD) tree (hereinafter referred to as KD-DBSCAN). The KD tree is used to divide the data set, construct the neighborhood object set, and distinguish the noise point and the core point in advance to avoid the calculation of the noise neighborhood set in the clustering process and speed up the neighborhood set query of the core point object. In this study, the global positioning system (GPS) data of a floating car is used as experimental data to compare the traditional DBSCAN algorithm and KD-DBSCAN algorithm in aspects of the clustering effect and time performance. The experimental results show that the KD-DBSCAN algorithm is comparable to the traditional DBSCAN algorithm in the clustering effect but has greatly improved time performance.