Sequential and Shared-Memory Parallel Algorithms for Partitioned Local Depths
This work designs, analyzes, and optimizes sequential and shared-memory parallel algorithms for partitioned local depths (PaLD). The algorithms identify pairwise relationships from relative distances and attain sequential speedups up to 29x over a baseline sequential implementation and parallel speedups up to 19.4x over optimized sequential implementations using up to 32 threads on an Intel multicore CPU.