TEA+ : A Novel Temporal Graph Random Walk Engine with Hybrid Storage Architecture

• DOI: 10.1145/3652604
• Publication Date: 2024-03-14T12:23:19Z
• Authors: Chengying Huan; Yongchao Liu; Heng Zhang; Shuaiwen Song; Santosh Pandey; Shiyang Chen; Xiangfei Fang; Yue Jin; Baptiste Lepers; Yanjun Wu; Hang Liu
• Keywords: 0301 basic medicine; 0202 electrical engineering, electronic engineering, information engineering

Many real-world networks are characterized by being temporal and dynamic, wherein the information signifies changes in connections, such as addition or removal of links between nodes. Employing random walks on these is a crucial technique for understanding structural evolution graphs over time. However, existing state-of-the-art sampling methods designed traditional static graphs, such, they struggle to efficiently handle dynamic aspects networks. This deficiency can be attributed several challenges, including increased complexity, extensive index space, limited programmability, lack scalability. In this article, we introduce TEA+ , robust, fast, scalable engine conducting graphs. Central an innovative hybrid method that amalgamates two Monte Carlo techniques. fusion significantly diminishes space complexity while maintaining fast speed. Additionally, integrates range optimizations enhance efficiency. further supported effective graph updating strategy, skilled managing modifications adeptly handling insertion deletion both edges vertices. For ease implementation, propose temporal-centric programming model, simplify development various walk algorithms To ensure optimal performance across storage constraints, features degree-aware architecture, capable scaling different memory environments. Experimental results showcase prowess it attains up three orders magnitude speedups compared current engines