Density peaks clustering (DP) has the ability of detecting clusters of
arbitrary shape and clustering non-Euclidean space data, but its quadratic
complexity in both computing and storage makes it difficult to scale for big
data. Various approaches have been proposed in this regard, including MapReduce
based distribution computing, multi-core parallelism, presentation
transformation (e.g., kd-tree, Z-value), granular computing, and so forth.
However, most of these existing methods face two limitations. One is their
target datasets are mostly constrained to be in Euclidian space, the other is
they emphasize only on local neighbors while ignoring global data distribution
due to restriction to cut-off kernel when computing density. To address the two
issues, we present a faithful and parallel DP method that makes use of two
types of vector-like distance matrices and an inverse leading-node-finding
policy. The method is implemented on a message passing interface (MPI) system.
Extensive experiments showed that our method is capable of clustering
non-Euclidean data such as in community detection, while outperforming the
state-of-the-art counterpart methods in accuracy when clustering large
Euclidean data. Our code is publicly available at
this https URL

通过使用两种向量距离矩阵和反向领先节点发现策略，我们提出了一种忠实且并行的密度峰值聚类方法，该方法能够在聚类大规模欧几里得数据时显示出优越的准确性，并且能够聚类非欧几里得数据，例如在社区检测中。

通过 MPI 并行计算系统进行矩阵计算的密度峰聚类算法

Faithful Density-Peaks Clustering via Matrix Computations on MPI  Parallelization System

This paper studies density-based clustering of point sets. These methods use
dense regions of points to detect clusters of arbitrary shapes. In particular,
we study variants of density peaks clustering, a popular type of algorithm that
has been shown to work well in practice. Our goal is to cluster large
high-dimensional datasets, which are prevalent in practice. Prior solutions are
either sequential, and cannot scale to large data, or are specialized for
low-dimensional data.
This paper unifies the different variants of density peaks clustering into a
single framework, PECANN, by abstracting out several key steps common to this
class of algorithms. One such key step is to find nearest neighbors that
satisfy a predicate function, and one of the main contributions of this paper
is an efficient way to do this predicate search using graph-based approximate
nearest neighbor search (ANNS). To provide ample parallelism, we propose a
doubling search technique that enables points to find an approximate nearest
neighbor satisfying the predicate in a small number of rounds. Our technique
can be applied to many existing graph-based ANNS algorithms, which can all be
plugged into PECANN.
We implement five clustering algorithms with PECANN and evaluate them on
synthetic and real-world datasets with up to 1.28 million points and up to 1024
dimensions on a 30-core machine with two-way hyper-threading. Compared to the
state-of-the-art FASTDP algorithm for high-dimensional density peaks
clustering, which is sequential, our best algorithm is 45x-734x faster while
achieving competitive ARI scores. Compared to the state-of-the-art parallel
DPC-based algorithm, which is optimized for low dimensions, we show that PECANN
is two orders of magnitude faster. As far as we know, our work is the first to
evaluate DPC variants on large high-dimensional real-world image and text
embedding datasets.

该研究论文通过抽象密度峰聚类算法中的关键步骤，如使用基于图的近似最近邻搜索（ANNS）方法来寻找满足预测函数的最近邻，提出了一种统一的框架 PECANN。通过在合成和真实数据集上评估，该方法在大规模高维度数据集上实现了高速的聚类效果，并在性能和准确性上超越了现有的算法。