.png){kind=icon}
.png){kind=icon}
Return
A Data Layout With Good Data Locality for Single-Machine Based Graph Engines
.png){kind=icon}
PRE
AI
DOI：10.1109/TC.2021.3107725.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Layout
Engines
Performance evaluation
Distributed databases
Central Processing Unit
Social networking (online)
Pattern matching
Data layout
data locality
graph engine
single machine
breadth first search
Journal
IF:
3.8
Papers:
5.3K
Citations:
9.8K