Fast proximity graph generation with spark
Arjun Subramanyam Varalakshmi, Chong Wang, Christoph F. Eick · 2019
Since the early 1980s, proximity graphs have served as one of the classical approaches to characterize neighborhood relationships; the most popular proximity graphs include Delaunay Triangulation (DT) and Gabriel graphs (GG). These graphs find their applications in geographical analysis, spatial analysis, pattern recognition, evolutionary biology, computer vision, cluster analysis, and visualization. The emergence of big data has created a need for scalable algorithms to generate proximity graphs for massive datasets. In this paper, we propose a novel approach for creating DT and GG by leveraging the cluster computing capabilities of Apache Spark. To compute DT, we rely on the divide and conquer paradigm. We first partition the spatial dataset into a grid; next, we compute the DT for each grid partition and separate the resulting triangles into the core and boundary triangles; next, we merge the adjacent partitions recursively and recompute boundary triangles; finally, we return the union of obtained triangles as the final result. GG generation is implemented on top of a DT, by removing edges from the DT not intersected with their corresponding Voronoi edge. We evaluate our proximity graph generation algorithms built on top of Spark to create DT and GG for a benchmark of datasets having between one and thirty million data records and compare our framework with existing Python and R libraries to create DT and GG. Our benchmark tests showcase significant performance improvements(2 times on DT and up to 24 times on GG) and the capability for creating DTs and GGs for datasets consisting of thirty million records.