In this work, we design, analyze, and optimize sequential and shared-memory parallel algorithms for partitioned local depths (PaLD). Given a set of data points and pairwise distances, PaLD is a method for identifying strength of pairwise relationships based on relative distances, enabling the identification of strong ties within dense and sparse communities even if their sizes and within-community absolute distances vary greatly. We design two algorithmic variants that perform community structure analysis through triplet comparisons of pairwise distances. We present theoretical analyses of computation and communication costs and prove that the sequential algorithms are communication optimal, up to constant factors. We introduce performance optimization strategies that yield sequential speedups of up to $29\times$ over a baseline sequential implementation and parallel speedups of up to $19.4\times$ over optimized sequential implementations using up to $32$ threads on an Intel multicore CPU.

我们设计、分析和优化基于分区本地深度（PaLD）的顺序和共享内存并行算法。通过对成对距离进行三元比较，我们设计了两种算法变体来执行社区结构分析。通过理论分析计算和通信成本，我们证明了顺序算法在通信上的最佳性能。我们介绍了性能优化策略，使得顺序实现相对于基线顺序实现加速高达29倍，并且在Intel多核CPU上使用32个线程时相对于优化顺序实现加速高达19.4倍。

分区局部深度的顺序和共享内存并行算法