USENIX ATC '23 - SOWalker: An I/O-Optimized Out-of-CoreGraph Processing System for Second-Order... скачать в хорошем качестве

USENIX ATC '23 - SOWalker: An I/O-Optimized Out-of-CoreGraph Processing System for Second-Order...

USENIX ATC '23 - SOWalker: An I/O-Optimized Out-of-Core Graph Processing System for Second-Order Random Walks Yutong Wu, Wuhan National Laboratory for Optoelectronics Huazhong University of Science and Technology, Zhan Shi, Wuhan National Laboratory for Optoelectronics Huazhong University of Science and Technology, Shicai Huang, Wuhan National Laboratory for Optoelectronics Huazhong University of Science and Technology, Zhipeng Tian, Wuhan National Laboratory for Optoelectronics Huazhong University of Science and Technology, Pengwei Zuo, Wuhan National Laboratory for Optoelectronics Huazhong University of Science and Technology, Peng Fang, Wuhan National Laboratory for Optoelectronics Huazhong University of Science and Technology, Dan Feng, Wuhan National Laboratory for Optoelectronics, Huazhong University of Science and Technology Random walks serve as a powerful tool for extracting information that exists in a wide variety of real-world scenarios. Different from the traditional first-order random walk, the second-order random walk considers recent walk history in selecting the next stop, which facilitates to model higher-order structures in real-world data. To meet the scalability of random walks, researchers have developed many out-of-core graph processing systems based on a single machine. However, the main focus of out-of-core graph processing systems is to support first-order random walks, which no longer perform well for second-order random walks. In this paper, we propose an I/O-optimized out-of-core graph processing system for second-order random walks, called SOWalker. First, we propose a walk matrix to avoid loading non-updatable walks and eliminate useless walk I/Os. Second, we develop a benefit-aware I/O model to load multiple blocks with the maximum accumulated updatable walks, so as to improve the I/O utilization. Finally, we adopt a block set-oriented walk updating scheme, which allows each walk to move as many steps as possible in the loaded block set, thus significantly boosting the walk updating rate. Compared with two state-of-the-art random walk systems, GraphWalker and GraSorw, SOWalker yields significant performance speedups (up to 10.2×). View the full USENIX ATC '23 program at https://www.usenix.org/conference/atc...