  Density peaks clustering has become a nova of clustering algorithm because of
its simplicity and practicality. However, there is one main drawback: it is
time-consuming due to its high computational complexity. Herein, a density
peaks clustering algorithm with sparse search and K-d tree is developed to
solve this problem. Firstly, a sparse distance matrix is calculated by using
K-d tree to replace the original full rank distance matrix, so as to accelerate
the calculation of local density. Secondly, a sparse search strategy is
proposed to accelerate the computation of relative-separation with the
intersection between the set of $k$ nearest neighbors and the set consisting of
the data points with larger local density for any data point. Furthermore, a
second-order difference method for decision values is adopted to determine the
cluster centers adaptively. Finally, experiments are carried out on datasets
with different distribution characteristics, by comparing with other six
state-of-the-art clustering algorithms. It is proved that the algorithm can
effectively reduce the computational complexity of the original DPC from
$O(n^2K)$ to $O(n(n^{1-1/K}+k))$. Especially for larger datasets, the
efficiency is elevated more remarkably. Moreover, the clustering accuracy is
also improved to a certain extent. Therefore, it can be concluded that the
overall performance of the newly proposed algorithm is excellent.
