Layph: Making Change Propagation Constraint in Incremental Graph Processing by Layering Graph

We implement Layph runtime engine based on Ingress[1] and Alibaba’s libgrape-lite[2].

Building Layph

Dependencies

Layph is developed and tested on Ubuntu 9.4.0. It should also work on other unix-like distributions. Building Layph requires the following softwares installed as dependencies.

• CMake (>=2.8)
• A modern C++ compiler compliant with C++-11 standard. (g++ >= 5.0)
• MPICH (>= 3.0) or OpenMPI (>= 3.0.0)
• glog (>= 0.3.4)
• gflags (>= 2.2.0);
• [boost](>= 1.65.1);

Building Layph and examples

mkdir build
cd build
cmake .. -DUSE_CILK=true
make layph
# run PageRank
mpirun -n 1 ./layph -application pagerank -vfile test.v -efile ../Dataset/test.base -efile_update ../Dataset/test.update -directed=1 -cilk=true -termcheck_threshold 0.000001 -app_concurrency 16 -compress=1 -portion=1 -build_index_concurrency=16 -max_node_num=5
# run single-source shortest path
mpirun -n 1 ./layph -application sssp -vfile test.v -efile ../Dataset/test_w.base -efile_update ../Dataset/test_w.update -directed=1 -cilk=true -app_concurrency 16 -compress=1 -portion=1 -sssp_source=0 -build_index_concurrency=16 -max_node_num=5

References

[1] Gong S, Tian C, Yin Q, et al. Automating incremental graph processing with flexible memoization[J]. Proceedings of the VLDB Endowment, 2021, 14(9): 1613-1625.

[2] Fan W, Xu J, Wu Y, et al. GRAPE: Parallelizing sequential graph computations[J]. Proceedings of the VLDB Endowment, 2017, 10(12): 1889-1892.

[3] Yu S, Gong S, Zhang Y, et al. Layph: Making Change Propagation Constraint in Incremental Graph Processing by Layering Graph[C]//2023 IEEE 39th International Conference on Data Engineering. IEEE, 2023: 2766-2779.