S M Shovan, a doctoral candidate in computer science, will defend their dissertation titled “Parallel Algorithms and Data Structure for Large-Scale Graph Analytics.” Their advisor, Dr. Sajal K. Das is an curators distinguished professor in computer science. The dissertation abstract is provided below.

Real-world graphs evolve continuously. Proteins bind and unbind in response to cellular signals, sensors join and leave networks as batteries deplete, roads close due to construction or disaster, and citation graphs grow as papers are published. As the graph changes, any property computed on its earlier state becomes stale. Recomputing these properties from scratch after every change is the obvious baseline, but it is catastrophically inefficient at the scales modern applications demand.

This dissertation develops scalable parallel algorithms for maintaining graph and hy-pergraph properties efficiently under continuous topological change. The unifying strategy is a two-step identify-and-update framework: given a batch of edge insertions and deletions, the framework identifies the affected subgraph in parallel, then iteratively propagates prop-erty updates within that bounded region until convergence. This principle avoids global recomputation and scales to networks with millions of vertices and billions of edges on shared-memory multi-core CPUs and massively parallel GPU architectures.

We apply this framework to four graph properties across six algorithms. For multi- objective shortest paths (MOSP), DynaMOSP achieves average speedups of 12.74→ on shared-memory CPUs and 69.19→ on Nvidia GPUs over state-of-the-art baselines, with peak speedups of 57.22→ and 105.39→, respectively. For dynamic hypergraph triad count-ing, ESCHER, the first GPU-based data structure for large dynamic hypergraphs, achieves speedups of up to 104.5→, 473.7→, and 112.5→ across three triad categories. Its memory- efficient successor ESCHER+ achieves approximately 110→ speedup with a significantly reduced memory footprint. For dynamic label propagation in graph-based semi-supervised learning, DynLP achieves an average speedup of 13→ (up to 102→) over state-of-the-art methods and up to 100→ better memory efficiency than dense harmonic-solution approaches.