Ligra-DAT: Graph-Level Edge-Density-Based Threshold Selection for Ligra

Abstract Ligra, a lightweight shared-memory multi-core graph processing framework, uses EDGEMAP with a static threshold (ρ = |E|/20) to switch between sparse and dense traversal modes. However, this static threshold does not account for edge-density differences among input graphs, which may cause delayed switching for low-density graphs and premature switching for high-density graphs. We propose Ligra-DAT, a graph-level edge-density-based threshold selection mechanism: after graph loading, it selects ρ × 1.5 for high-density graphs (δ > 0.1) to delay dense-mode switching and ρ × 0.7 for low-density graphs (δ ⩽ 0.1) to accelerate dense-mode switching. The selected threshold is then reused during EDGEMAP execution and is not retuned at each traversal iteration. Experiments on a 64-core server with 8 datasets and 6 core algorithms show that Ligra-DAT achieves up to 42.4% runtime reduction, preserves compatibility with Ligra applications, has O(1) threshold-selection complexity, and incurs overhead less than 0.1% of the corresponding Ligra execution time.