BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers

• DOI: 10.48550/arxiv.2405.11671
• Publication Date: 2024-05-19
• Authors: Brian Wheatman; Xiaojun Dong; Zheqi Shen; Laxman Dhulipala; Jakub Łącki; Prashant Pandey; Helen Xu
• Keywords: Benchmarking

A fundamental building block in any graph algorithm is a container - data structure used to represent the graph. Ideally, enables efficient access underlying graph, has low space usage, and supports updating efficiently. In this paper, we conduct an extensive empirical evaluation of containers designed support running algorithms on large graphs. To our knowledge, first apples-to-apples comparison rather than overall systems, which include confounding factors such as differences implementations infrastructure. We measure time 10 highly-optimized across over 20 different Somewhat surprisingly, find that average does not differ much containers, especially those dynamic updates. Specifically, simple based off-the-shelf B-tree only 1.22x slower highly optimized static one. Moreover, observe simplifying graph-container Application Programming Interface (API) few functions incurs mere 1.16x slowdown compared complete API. Finally, also batch-insert throughput dynamic-graph for full picture their performance. perform benchmarks, introduce BYO, unified framework standardizes evaluations graph-algorithm performance containers. BYO extends Graph Based Benchmark Suite (Dhulipala et al. 18), state-of-the-art benchmark, easily plug into enable fair comparisons between them suite algorithms. While several benchmarks have been developed date, best system benchmark