Essentials of Parallel Graph Analytics

We identify the graph data structure, frontiers, operators, an iterative loop structure, and convergence conditions as essential components of graph analytics systems based on the native-graph approach. Using these essential components, we propose an abstraction that captures all the significant pro...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-12
Main Authors: Muhammad Osama, Porumbescu, Serban D, Owens, John D
Format: Article
Language:English
Subjects:
Data structures
Iterative methods
Mathematical analysis
Message passing
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We identify the graph data structure, frontiers, operators, an iterative loop structure, and convergence conditions as essential components of graph analytics systems based on the native-graph approach. Using these essential components, we propose an abstraction that captures all the significant programming models within graph analytics, such as bulk-synchronous, asynchronous, shared-memory, message-passing, and push vs. pull traversals. Finally, we demonstrate the power of our abstraction with an elegant modern C++ implementation of single-source shortest path and its required components.
ISSN:2331-8422
DOI:10.48550/arxiv.2212.08200