streaming-heterogenous-sampling

Programs corresponding to the work "SMaSH: Streaming MST with Sampling on Heterogeneous Systems"

In this work, we study the maintenance of the Minimum Spanning Forest (MSF) under streaming edge updates (insertions, deletions, and modifications). This repo contains the CPU and GPU heterogeneous implementations for handling streaming updates using three core algorithmic variants: PDS, RES, and FRESH.

Dependencies

• python 3.7+
• CUDA Version 11.0+
• g++ version 7.3.0+ compiler
• OpenMP version 4.5+

Run

The helper dispatcher script run.py can be used to execute and benchmark the programs on a Linux/Linux-like Environment.

usage: run.py [-h] -a {pds,res,fresh} [-d DATASET] [-q QUERY] [-o OUTFILE] [-g] [-r]

optional arguments:
  -h, --help            show this help message and exit
  -a ALGO, --algorithm ALGO
                        pds - Prune-Directed Search, res - Reservoir-based, fresh - Filter-Reservoir Hybrid (Required)
  -d DATASET, --dataset DATASET
                        Base graph file path (default: datasets/graph.txt)
  -q QUERY, --query QUERY
                        Update stream query file path (default: datasets/updates.txt)
  -o OUTFILE, --outfile OUTFILE
                        Output file name to save experiment logs
  -g, --gpu             Run experiment on GPU (default: multicore CPU)
  -r, --recompile       Recompile executables

For example, to run the FRESH algorithm on the CPU:

python3 run.py --algorithm fresh 

To run the PDS algorithm on the GPU using a custom dataset and save the output in my_outfile.txt:

python3 run.py --algorithm pds --dataset datasets/graph.txt --query datasets/updates.txt --gpu --outfile my_outfile.txt

---

Dataset Generation

We have provided three optimized synthetic graph and stream generators in the queries/ subdirectory:

• Watts-Strogatz Generator: python3 queries/gen_ws_graph.py --vertices 10000 --neighbors 6 --stats (saves to datasets/graph.txt)
• Power-Law (Barabási-Albert) Generator: python3 queries/gen_pl_graph.py --vertices 10000 --edges-per-vertex 5 --stats (saves to datasets/graph.txt)
• Update Stream Generator: python3 queries/gen_updates.py --vertices 10000 --updates 20000 --input-graph datasets/graph.txt (saves to datasets/updates.txt)