Paper link: https://dl.acm.org/doi/pdf/10.1145/3448016.3457253
This repository contains code for our SIGMOD paper "Cache-Efficient Fork-Processing Patterns on Large Graphs". It is implemented based on Julian Shun's Ligra https://github.com/jshun/ligra
Compiler:
- g++ >= 7.5.0
Build system:
- CMake >= 3.12
To build:
$ cd ForkGraph/ # go to the source folder
$ mkdir build
$ cd build && cmake ..We support the adjacency graph format used by the Problem Based Benchmark suite and Ligra.
The adjacency graph format starts with a sequence of offsets one for each vertex, followed by a sequence of directed edges ordered by their source vertex. The offset for a vertex i refers to the location of the start of a contiguous block of out edges for vertex i in the sequence of edges. The block continues until the offset of the next vertex, or the end if i is the last vertex. All vertices and offsets are 0 based and represented in decimal. The specific format is as follows:
AdjacencyGraph
<n>
<m>
<o0>
<o1>
...
<o(n-1)>
<e0>
<e1>
...
<e(m-1)>
This file is represented as plain text.
Weighted graphs are represented in the weighted adjacency graph format. The file should start with the string "WeightedAdjacencyGraph". The m edge weights should be stored after all of the edge targets in the .adj file.
Using SNAP graphs
Graphs from the SNAP dataset collection are commonly used for graph algorithm benchmarks. Pleae use the tool that converts the most common SNAP graph format to the adjacency graph format that ForkGraph accepts. The tool can be found in GBBS: Graph Based Benchmark Suite.
If you use ForkGraph in your paper, please cite our work (here).
@inproceedings{lu2021cache,
title={Cache-Efficient Fork-Processing Patterns on Large Graphs},
author={Lu, Shengliang and Sun, Shixuan and Paul, Johns and Li, Yuchen and He, Bingsheng},
booktitle={Proceedings of the 2021 International Conference on Management of Data},
pages={1208--1221},
year={2021}
}