Introduction
The Graph-Based Benchmark Suite (GBBS) is an active research project to build provably-efficient, scalable, single-machine implementations for a broad set of fundamental graph problems. Our approach is to design simple algorithm implementations that rely on high-level functional grpah and vertex primitives that have well-defined cost-bounds in the work-depth model. The project is in development at both CMU and MIT, and has been used to implement over 20 problems so far.
Getting Started#
This part of the site provides instructions for installing, compiling, and running the codes provided in GBBS. It also provide details on the graph formats supported by GBBS.
- Installation provides instructions on system requirements and how to download and install GBBS.
- Compilation explains how to compile benchmarks in
GBBS using both our build-tool,
bazel, and usingmake. - Graph Formats describes the graph formats supported by our implementations.
- Running explains how to run a benchmark on our graph inputs.
- Graph Inputs describes the main graph inputs used in our experiments, and provides details on how to obtain them.
Benchmarks#
This part of the site provides a problem-based benchmark specifications for each of the problems supported by GBBS. Links to the benchmarks can be found below:
Shortest Path Problems#
- Breadth-First Search
- Integral-Weight SSSP
- Positive-Weight SSSP
- General-Weight SSSP
- Single-Source Widest Path
- Single-Source Betwenness Centrality
- Graph Spanner
Connectivity Problems#
- Low-Diameter Decomposition
- Connectivity
- Biconnectivity
- Spanning Forest
- Minimum Spanning Forest
- Strongly Connected Components
Covering Problems#
Substructure Problems#
- Triangle Counting
- -Clique Counting
- -Core
- -Truss
- Approximate Densest Subgraph
- Low-Outdegree Orientation (Arboricity Ordering)
Eigenvector Problems#
References#
A list of publications built using GBBS and contributing to the benchmark can be found here.