Loading Events

« All Events

  • This event has passed.

M.Tech Research Thesis {Colloquium} ONLINE: CDS: 18th January 2022 : ” Optimising the Interval-centric Distributed Computing Model for Temporal Graph Algorithms”

18 Jan @ 2:00 PM -- 3:00 PM

DEPARTMENT OF COMPUTATIONAL AND DATA SCIENCES
M.Tech Research  Thesis Colloquium

Speaker                 : Mr. Animesh Baranawal

S.R. Number         : 06-18-02-10-22-19-1-16610

Title                       : “Optimising the Interval-centric Distributed Computing Model for Temporal Graph Algorithms“​
Date & Time         : January 18, 2022 (Tuesday), 02:00 PM
Research Supervisor: Prof. Yogesh Simmhan
Venue                     : Online

Abstract

Graphs with temporal characteristics are increasingly becoming prominent. Their vertices, edges and attributes are annotated with a lifespan, allowing one to add or remove vertices and edges. Such graphs can grow to millions of vertices, billions of edges, and have months or years of data. Time-dependent algorithms such as temporal reachability and shortest paths are designed over such materialised graphs. These algorithms find important use-cases in digital contact tracing, optimising transit routes, and analysing information diffusion over temporal graphs. Interval-centric Computing (ICM) is a recent abstraction over temporal graphs, enabling easy development of temporal algorithms while ensuring efficient computation and communication. To ease the design of temporal algorithms, ICM introduces a novel TimeWarp phase associated with a warp operator. However, this warp operator is super-linear in time complexity with the number of messages received at a vertex. Further, in pipelining the computation and communication phases, ICM may create stale or redundant messages.

 

We propose three different techniques to accelerate the execution model of ICM: Local Warp Unrolling (LU), Deferred Message Scatter (DS) and Windowed ICM (WICM). LU unrolls the messages processed in the TimeWarp phase to reduce the time complexity of the warp operator. DS results in lazy scatter operations that reduce redundant calls to messaging. WICM partitions the temporal graphs along the temporal dimension and processes the subgraphs in parts, ensuring proper carryover of vertex states. While LU and DS apply locally to each vertex, WICM is applicable at the global graph level and can be used along with the other two techniques. These optimisations do not require any change to the graph algorithms designed using ICM. Further, we also prove the equivalence of this execution model to ICM’s execution for a large class of temporal traversal

algorithms. For WICM, not all temporal partitioning strategies give the same execution performance. We also develop heuristics using global graph topology with analytical modelling of TimeWarp to determine the partitioning used with WICM.

 

We extensively evaluate six large temporal graphs with up to 133M vertices, 5.5B edges and 365 snapshots, and six graph algorithms on an 8-node commodity cluster. LU+DS reduce the runtime of ICM by an average of 56%; WICM reduces the runtime by 48% on average over native ICM, and combining these techniques offers an average reduction of 61%. We also conduct experiments to evaluate the effectiveness of the heuristic partitioning technique. Because of temporal partitioning, not all partitions of the graph are required simultaneously. As future work, WICM can also be used incrementally, reducing the application’s memory footprint.

Details

Date:
18 Jan
Time:
2:00 PM -- 3:00 PM

Venue

Online