@article{Ban2026, 
author = {Zhaoqin Ban and Xinxin Yang and Dapeng Fu and Tengfei Cao and Jianqiang Huang},
title = {Ligra-DAT: Graph-Level Edge-Density-Based Threshold Selection for Ligra},
year = {2026},
journal = {Tsinghua Science and Technology},
keywords = {Graph Processing, Shared Memory, Ligra, Edge-Density-Based Threshold Selection, Edge Density},
url = {https://www.sciopen.com/article/10.26599/TST.2026.9010089},
doi = {10.26599/TST.2026.9010089},
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.}
}