In Partial Fulfillment of the Requirements for the Degree of Master of Science

Arjun Subramanyam Varalakshmi

will defend his thesis

Transforming Point Data into Proximity Graphs

Abstract

Establishing neighborhood relationships among data points is essential for several data analysis applications, for which structural information is important. Since the early 1980’s, Proximity Graphs served as one of the classical approaches to characterize neighborhood relationships; the most popular Proximity Graphs include Delaunay Triangulation (DT), Gabriel graphs (GG), Relative Neighbor Graphs (RNG) and Minimal Spanning Tree. These graphs find their applications in geographical variation analysis, spatial analysis, pattern recognition, evolutionary biology, computer vision, cluster analysis, and visualization. In this thesis, we develop parallel algorithms for computing Delaunay Triangulations, Gabriel graphs, and Relative Neighbor Graphs by leveraging cluster computing capabilities of Apache Spark. Our DT algorithm partitions the dataset across the compute nodes in the cluster. Next we compute DTs locally for each partition and partition the obtained triangles into two sets: final triangles and non-final triangles. Finally, we post-process the non-final triangles and return the union of all the triangles as a result. Our GG and RNG algorithms are built on top of DT, removing edges from the DT. We evaluate the developed algorithms for a benchmark of massive dataset, and the results show significant speedups over sequential implementations of the same algorithms.

Date: Friday, April 20, 2018
Time: 2:30 PM
Place: PGH 362
Advisor: Dr. Christoph F. Eick

Faculty, students, and the general public are invited.