A Data Layout With Good Data Locality for Single-Machine Based Graph Engines

Yong Yeon Jo, Myung Hwan Jang, Sang Wook Kim, Sunju Park

Research output: Contribution to journalArticlepeer-review


Graph engines have been used in many applications to handle big graphs efficiently. The majority of the research to improve their performance has focused primarily on the design of efficient graph processing. This paper claims, however, the focus should be given also to graph storage design. This is because good storage design can improve both CPU performance and I/O performance of graph engines. In this paper, we propose an efficient data layout for single-machine based graph engines. We identify the common node access pattern of the graph algorithms running on single-machine based graph engines. Based on this finding, we propose the breadth-first (BF) data layout which places the nodes processed together in the same or adjacent storage space so that they can be accessed together as much as possible. The experimental results show that the BF data layout improves both CPU and I/O performances significantly in all single-machine based graph engines.

Original languageEnglish
Pages (from-to)1784-1793
Number of pages10
JournalIEEE Transactions on Computers
Issue number8
Publication statusPublished - 2022 Aug 1

Bibliographical note

Publisher Copyright:
© 1968-2012 IEEE.

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'A Data Layout With Good Data Locality for Single-Machine Based Graph Engines'. Together they form a unique fingerprint.

Cite this