Research Projects

A graph represents the pairwise relationships between objects or entities that underlie the complex frameworks such as blockchains, social networks, semantic-web, biological networks and many others. The contemporary applications of graph algorithms in real-time analytics, such as product recommendation or influential user tracking over social network graphs, demand dynamic addition and removal of vertices and/or edges over time. Existing approaches for graph analytics can be broadly classified in batch analytics, e.g. GraphTinker where a graph operation is performed over a static temporal snapshot of the data structure, and stream analytics e.g. Kineograph, where a temporal window of incoming data is studied. Recent trends show that there is an emerging niche for the analytics tasks closer to the data sources, such as mobile and edge devices [4]. On such platforms, though multi-core is getting progressively ubiquitous [5], memory is limited. Therefore the graph applications with unbounded dynamic updates must aim to have a lightweight memory footprint. In substance, the pursuit of an efficient lightweight real-time parallel graph analytics framework with a fresh design approach is imperative. In this proposal, we plan to develop lock-free and wait-free concurrent graph libraries for dynamic graph analytics. By design these methods being lock-free, wait-free, are automatically non-blocking as well. We want this library to lightweight. Another important requirement of a concurrent data structure is to formally prove and verify its correctness. We also formally attempt to prove and verify the correctness of the proposed concurrent graph library and the resulting implementation.