The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	Accelerating transitive closure of large-scale sparse graphs
Author:	Patel, Sanyamee Milindkumar
View Online:	njit-etd2020-075 (x, 56 pages ~ 0.7 MB pdf)
Department:	Department of Computer Science
Degree:	Master of Science
Program:	Computer Science
Document Type:	Thesis
Advisory Committee:	Bader, David A. (Committee chair) Koutis, Ioannis (Committee member) Theodoratos, Dimitri (Committee member)
Date:	2020-12
Keywords:	Transitive closuer Graph representations Real world systems Anti-section parallel implementations
Availability:	Unrestricted
Abstract:	Finding the transitive closure of a graph is a fundamental graph problem where another graph is obtained in which an edge exists between two nodes if and only if there is a path in our graph from one node to the other. The reachability matrix of a graph is its transitive closure. This thesis describes a novel approach that uses anti-sections to obtain the transitive closure of a graph. It also examines its advantages when implemented in parallel on a CPU using the Hornet graph data structure. Craph representations of real-world systems are typically sparse in nature due to lesser connectivity between nodes. The anti-section approach is designed specifically to improve performance for large scale sparse graphs. The NVIDIA Titan V CPU is used for the execution of the anti-section parallel implementations. The Dual-Round and Hash-Based implementations of the Anti-Section transitive closure approach provide a significant speedup over several parallel and sequential implementations.