数据分布策略的调查与实验回顾——用于并行空间聚类算法
A Survey and Experimental Review on Data Distribution Strategies for Parallel Spatial Clustering Algorithms
-
摘要:研究背景 大数据的出现导致并行集群算法的使用快速增长，这些算法在 MPI、MapReduce 和 Spark 等分布式计算框架上运行。这种并行算法可以在非常大的数据集上高效地执行聚类，否则这在顺序计算机上几乎是不可能的或效率极低。在分布式内存的并行集群算法的情况下，一个重要的步骤是数据在集群节点之间的分布。此步骤控制整个算法的方法和性能。研究人员通常根据算法的要求使用随机或空间/几何分布策略，例如基于 kd 树的分区和基于网格的分区。然而，这些策略是通用的，并不是为任何特定的并行聚类算法量身定制的。我们需要特定的数据分布策略来使每种算法更加高效。目的 本文有两个主要目标。第一个目标是对基于 MPI 的并行聚类算法进行全面的文献调查，特别是它们采用的具体数据分布策略。第二个目标是提出三种量身定制的数据分布策略：用于并行基于密度的聚类算法（如 DBSCAN 和 OPTICS）的参数化维度分割，用于 dGridSLINK 的基于单元的维度分割，dGridSLINK 是基于网格的层次聚类算法，在不相交空间上表现出高效性分布，以及基于投影的分割，这是一种通用的分布策略。方法 正如目标中提到的，我们首先对基于 MPI 的并行聚类算法进行非常全面的文献调查。对于每种算法，都特别强调其采用的特定数据分布策略及其对其性能的影响。我们还总结了基于各种架构的其他并行聚类算法，包括共享内存架构、GP-GPU 架构、MapReduce 和 Spark。然后，我们提出了三种新的数据分布策略，即：用于 DBSCAN 和 OPTICS 等基于密度的并行聚类算法的参数化维度分割，用于 dGridSLINK 的基于单元的维度分割，这是基于网格的层次聚类算法，在不相交空间分布方面表现出效率，以及基于投影的分割，这是一种通用的分发策略。所有这些都保留了空间局部性，实现了不相交分区，并确保了良好的数据负载平衡。我们进行了广泛的实验分析，其中我们使用所提出的数据分布策略而不是现有的数据分布策略来运行每个并行聚类算法。在这些实验的基础上，我们对其使用给出了适当的建议。结果 实验结果给出了有关所提出的数据分布技术的使用的以下观察结果和建议：（i）对于并行 DBSCAN（以及涉及邻域计算的类似 DBSCAN 的算法），PD-Split 和 KD-Split 具有竞争力。PD-Split更适合较小的ε值和高维数据集。对于较大的 ε 值，建议使用 KD-Split。 (ii) 对于并行共享最近邻聚类 (dR-SNN) 和使用 kNN 查询的算法，KD-Split 总是效果更好。 (iii) 对于并行dGridSLINK算法，CD-Split一直优于KD-Split和Pbased-Split。始终建议使用它。 (iv) 当人们只想跨一个维度进行分割时，可以使用 Pbased-Split 作为一种通用的分布方案，无需参数。在某些情况下，Pbased-Split 对于高维数据也很有效（见图10f）。 (v) 建议将 PD-Split 和 Pbased-Split 用于异构架构和低带宽网络互连，因为它们可以最大限度地减少光环区域的面积。结论 本文讨论并行聚类算法的一个重要方面，即数据分布步骤。这是第一篇论文，对并行聚类算法中使用的数据分布策略进行了全面的回顾和比较研究，同时提出了三种新策略，即 PD-Split、CD-Split 和 Pbased-Split。实验证明，与最先进的方法相比，这些新策略可以提高各自算法的性能。实验还证明了使用上述策略的适当建议。本文还对基于 MPI 的并行聚类算法进行了非常全面的回顾，并具体讨论了它们使用的数据分布策略。作为所提议工作的扩展，可以开发网格和 PD-Split 的混合设计，以更有效地为 GridDBSCAN-D 工作。此外，还可以为其他架构（例如共享内存、GP-GPU、MapReduce 和 Spark）开发此类策略。另外，可以为其他类别的并行聚类算法（例如子空间和基于网格的聚类）开发更多此类定制的分布策略。Abstract: The advent of Big Data has led to the rapid growth in the usage of parallel clustering algorithms that work over distributed computing frameworks such as MPI, MapReduce, and Spark. An important step for any parallel clustering algorithm is the distribution of data amongst the cluster nodes. This step governs the methodology and performance of the entire algorithm. Researchers typically use random, or a spatial/geometric distribution strategy like kd-tree based partitioning and grid-based partitioning, as per the requirements of the algorithm. However, these strategies are generic and are not tailor-made for any specific parallel clustering algorithm. In this paper, we give a very comprehensive literature survey of MPI-based parallel clustering algorithms with special reference to the specific data distribution strategies they employ. We also propose three new data distribution strategies namely Parameterized Dimensional Split for parallel density-based clustering algorithms like DBSCAN and OPTICS, Cell-Based Dimensional Split for dGridSLINK, which is a grid-based hierarchical clustering algorithm that exhibits efficiency for disjoint spatial distribution, and Projection-Based Split, which is a generic distribution strategy. All of these preserve spatial locality, achieve disjoint partitioning, and ensure good data load balancing. The experimental analysis shows the benefits of using the proposed data distribution strategies for algorithms they are designed for, based on which we give appropriate recommendations for their usage.
下载: