DIST

Supplementary materials for DIST: Efficient k-Clique Listing via Induced Subgraph Trie

Dependencies

• g++ compiler with c++17 support
• jemalloc

Usage

make

Finding 5-cliques in ca-AstroPh dataset using a single core.

LD_PRELOAD=/usr/lib64/libjemalloc.so.1 ./DIST --k=5 --graph=./dataset/ca-AstroPh.edges

Finding 5-cliques in ca-AstroPh dataset using 24 cores.

LD_PRELOAD=/usr/lib64/libjemalloc.so.1 ./DIST-parallel --threads=24 --k=5 --graph=./dataset/ca-AstroPh.edges

For large k values in large-ω datasets, the early-termination technique is used (Enabled by -D_EARLY_TERMINATION).

Input file contains the list of edges.

Example

0 1
0 2
1 2
1 3
1 4
2 3
3 4