Search papers, labs, and topics across Lattice.
This paper investigates the discrepancies between synthetic and natural edge weight distributions in the evaluation of Parallel Single-Source Shortest Path (SSSP) algorithms. By analyzing 17 real-world graphs and contrasting their heavy-tailed weight distributions with six commonly used synthetic distributions, the authors reveal that current benchmarking practices may significantly bias algorithm performance. The study finds that using synthetic uniform weights can lead to suboptimal parameter tuning and even reverse the expected performance rankings of state-of-the-art SSSP algorithms.
Evaluating SSSP algorithms with synthetic weights can invert their performance hierarchy, revealing a critical flaw in current benchmarking practices.
Scientific research works often evaluate Parallel Single-Source Shortest Path (SSSP) algorithms using synthetic, uniformly distributed edge weights. However, real-world graphs exhibit very different, often heavy-tailed, weight distributions. This creates a disconnect between how algorithms are evaluated and their real-world performance, since most SSSP implementations inherently rely on the weight distribution for parameter tuning and work efficiency. In this paper, we explore whether current benchmarking methods unintentionally bias the performance results of these algorithms. To this end, we statistically characterize the weight distributions of 17 real-world graphs from a variety of domains and contrast them with six synthetic distributions used in the literature. Through a comprehensive evaluation of seven state-of-the-art parallel SSSP algorithms, we demonstrate severe sensitivity to edge weights, and show that evaluating with synthetic uniform weights alters optimal parameter configurations and can invert the performance hierarchy. These findings challenge existing benchmarking standards and offer practical insights for rigorous SSSP algorithm design.
