KGraph: Concurrent Graph Query Processing with Memoization on Graph

Organization

This repository contains the code for KGraph. It is implemented based on ForkGraph.

Compilation

Compiler:

g++ >= 7.5.0

Build system:

CMake >= 3.12

To build:

$ cd KGraph/
$ mkdir build
$ cd build && cmake ..

Input Graph Formats

The input graph comprises three files: <inFile_inter>, <inFile_intra> and <partFile>. The <inFile_inter> file contains the inter-partition edges, the <inFile_intra> file contains the intra-partition edges, and the <partFile> file contains the partition information. The number in the i-th line corresponds to the partition ID of the vertex with vertex ID i-1.

<inFile_inter> and <inFile_intra> should be in the weighted adjacency graph format used by the Problem Based Benchmark suite and Ligra. We provide some example graphs in this format in the shared OneDrive folder.

Usage

Note:

For traversal-based applications, we implement two versions: sparse and dense. The sparse version is suitable for road networks and other graphs with low average degree, while the dense version is suitable for power-law graphs.

The choose of some parameters is crucial for the performance of KGraph and should be carefully tuned based on hardware resource (LLC size, number of processors and CPUs). We provide some recommended values for these parameters.

Common parameters for all applications

$ ./kgraph-app -p <#part> -ps <strategy> -pn <#pivot> -qn <#query> -qf <inSrc> <inFile_inter> <inFile_intra> <partFile>

Argument	Description
-p	The number of partitions
-ps -pn	The strategy for seleting pivots The number of pivots
-qn -qf	The number of queries to be evaluated The file containing source vertices of queries
<inFile_inter> <inFile_intra> <partFile>	The input Graph

Specific parameters for each application

Argument	Application	Description
-h	`kgraph-sssp-sparse` `kgraph-sswp-sparse` `kgraph-ssr-sparse`	The heuristic-Based Yielding used in ForkGraph. We recomand setting it to 3200 for `Ca` and `Us`, and 204800 for `Eu`.
-mr	`kgraph-sssp-dense` `kgraph-sswp-dense` `kgraph-ssr-dense`	The extent of memoization for a pivot. The larger this value is, the more information the pivot will memoize, but it will also consume more memory. `[default: 2]`
-wl	`kgraph-deepwalk` `kgraph-ppr`	The walk length. `[default: 1000]`
-ml	`kgraph-deepwalk` `kgraph-ppr`	The length of a path memoized by a pivot that starts from itself. We recomand setting it to 4 for road networks and 2 for power-law graphs.