Scalable Parallel OPTICS Data Clustering Using Graph Algorithmic Techniques

OPTICS is a hierarchical density-based data clustering algorithm that discovers arbitrary-shaped clusters and eliminates noise using adjustable reachability distance thresholds. Parallelizing OPTICS is considered challenging as the algorithm exhibits a strongly sequen-tial data access order. We present a scalable parallel OPTICS algo-rithm (POPTICS) designed using graph algorithmic concepts. To break the data access sequentiality, POPTICS exploits the similar-ities between the OPTICS algorithm and PRIM’s Minimum Span-ning Tree algorithm. Additionally, we use the disjoint-set data structure to achieve a high parallelism for distributed cluster ex-traction. Using high dimensional datasets containing up to a billion floating point numbers, we show scalable speedups of up to 27.5 for our OpenMP implementation on a 40-core shared-memory ma-chine, and up to 3,008 for our MPI implementation on a 4,096-core distributed-memory machine. We also show that the quality of the results given by POPTICS is comparable to those given by the clas-sical OPTICS algorithm