Compile- and run-time approaches for the selection of efficient data structures for dynamic graph analysis

Area of Science:

• Computer Science
• Data Science
• Algorithm Analysis

Background:

• Dynamic graphs are prevalent in various fields like social network analysis and big data processing.
• Analyzing high-frequency dynamic graphs demands high performance, which is sensitive to data structure choices.
• Selecting optimal data structures for dynamic graph analysis is challenging, even for expert programmers.

Purpose of the Study:

• To automatically select the most efficient data structures for dynamic graph analysis.
• To extend previous compile-time approaches with a measurement study and cost estimation functions.
• To develop a run-time approach for dynamic graph analysis with non-constant workloads.

Main Methods:

• Conducted a measurement study of seven data structures for dynamic graph analysis.
• Developed and evaluated a compile-time approach for selecting data structures based on estimated costs.
• Implemented and analyzed a run-time approach with live profiling and automatic data structure exchange.

Main Results:

• The compile-time approach achieved speedups of up to 5.4× for real-world dynamic graphs with constant workloads.
• The run-time approach achieved speedups of up to 7.3× for artificial non-constant workloads.
• Both approaches demonstrated significant performance improvements over basic data structure configurations.

Conclusions:

• Automated data structure selection significantly enhances dynamic graph analysis performance.
• The run-time approach effectively addresses the limitations of static, compile-time methods for non-constant workloads.
• This work provides practical solutions for optimizing performance in dynamic graph processing.