Sequential and Shared-Memory Parallel Algorithms for Partitioned Local Depths
This work provides efficient algorithms for community structure analysis, but it is incremental as it focuses on optimizing existing PaLD methods.
The paper tackled the problem of identifying strong pairwise relationships in data with varying community sizes and distances by designing sequential and parallel algorithms for partitioned local depths (PaLD), achieving sequential speedups up to 29× and parallel speedups up to 19.4× with 32 threads.
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.