Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds

Chatterjee, B. and Peri, Sathya and Sa, M. and et al, . (2022) Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds. In: 25th International Conference on Principles of Distributed Systems, OPODIS 2021, 13 December 2021 through 15 December 2021, Strasbourg.

Text
Leibniz_International_Proceedings_in_Informatics1.pdf - Published Version
Available under License Creative Commons Attribution.
Download (2MB)

Abstract

Today’s graph-based analytics tasks in domains such as blockchains, social networks, biological networks, and several others demand real-time data updates at high speed. The real-time updates are efficiently ingested if the data structure naturally supports dynamic addition and removal of both edges and vertices. These dynamic updates are best facilitated by concurrency in the underlying data structure. Unfortunately, the existing dynamic graph frameworks broadly refurbish the static processing models using approaches such as versioning and incremental computation. Consequently, they carry their original design traits such as high memory footprint and batch processing that do not honor the real-time changes. At the same time, multi-core processors–a natural setting for concurrent data structures–are now commonplace, and the analytics tasks are moving closer to data sources over lightweight devices. Thus, exploring a fresh design approach for real-time graph analytics is significant. This paper reports a novel concurrent graph data structure that provides breadth-first search, single-source shortest-path, and betweenness centrality with concurrent dynamic updates of both edges and vertices. We evaluate the proposed data structure theoretically – by an amortized analysis – and experimentally via a C++ implementation. The experimental results show that (a) our algorithm outperforms the current state-of-the-art by a throughput speed-up of up to three orders of magnitude in several cases, and (b) it offers up to 80x lighter memory-footprint compared to existing methods. The experiments include several counterparts: Stinger, Ligra and GraphOne. We prove that the presented concurrent algorithms are non-blocking and linearizable. © Bapi Chatterjee, Sathya Peri, Muktikanta Sa, and Komma Manogna.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Peri, Sathya	UNSPECIFIED

Item Type:

Conference or Workshop Item (Paper)

Additional Information:

Funding This work was partially funded by National Supercomputing Mission, Govt. of India under the project “Concurrent and Distributed Programming primitives and algorithms for Temporal Graphs”(DST/NSM/R&D_Exascale/2021/16).

Uncontrolled Keywords:

Betweenness centrality, Breadth-first search, Concurrent data structure, Directed graph, Linearizability, Non-blocking, Single-source shortest-path

Subjects:

Computer science

Divisions:

Department of Computer Science & Engineering

Depositing User:

. LibTrainee 2021

Date Deposited:

13 Jul 2022 12:16

Last Modified:

13 Jul 2022 12:16