MITra: A Framework for Multi-Instance Graph Traversal

Jia Li, Wenyue Zhao, Nikos Ntarmos, Yang Cao, Peter Buneman

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

This paper presents MITra, a framework for composing multi-instance graph algorithms that traverse from multiple source vertices simultaneously over a single thread. Underlying MITra is a model of multi-instance traversal that uniformly captures traversal sharing across instances. Based on this, MITra provides a programming model that allows users to express traversals by declaring vertex ranks and specify computation logic via an edge function. It synthesizes multi-instance traversal algorithms from declared vertex ranks and edge functions adopted from classic single-instance algorithms, automatically sharing computation across instances and benefiting from SIMD. We show that MITra can generate multi-instance algorithms provably better than existing ones, while being more expressive than traditional frameworks. In addition to the ease of programming, we experimentally verify that MITra is on average an order of magnitude faster than approaches based on existing frameworks for common graph algorithms, and is comparable to the state-of-the-art highly optimized one-off algorithms.
Original languageEnglish
Pages (from-to)2551-2564
Number of pages14
JournalProceedings of the VLDB Endowment
Issue number10
Publication statusPublished - 8 Aug 2023
EventThe 49th International Conference on Very Large Data Bases, 2023 - Vancouver, Canada
Duration: 28 Aug 20231 Sept 2023
Conference number: 49


Dive into the research topics of 'MITra: A Framework for Multi-Instance Graph Traversal'. Together they form a unique fingerprint.

Cite this