VENUS: A System for Streamlined Graph Computation on a Single PC
Publication in refereed journal


摘要Recent studies show that disk-based graph computation systems on just a single PC can be as highly competitive as cluster-based systems on large-scale problems. Inspired by this remarkable progress, we develop VENUS, a disk-based graph computation system which is able to handle billion-scale graphs efficiently on a commodity PC. VENUS adopts a novel computing architecture that features vertex-centric "streamlined" processing-the graph is sequentially loaded and an update function is executed for each vertex in parallel on the fly. VENUS deliberately avoids loading batch edge data by separating read-only structure data from mutable vertex data on disk, and minimizes random IOs by caching vertex data in the main memory whenever possible. The streamlined processing is realized with efficient sequential scan over massive structure data and fast feeding the update function for a large number of vertices. Extensive evaluation on large real-world and synthetic graphs has demonstrated the efficiency of VENUS. For example, to run the PageRank algorithm on a Twitter graph of 42 million vertices and 1.4 billion edges, Spark needs 8.1 minutes with 50 machines and GraphChi spends 13 minutes using high-speed SSD, while VENUS only takes 5 minutes on one machine with an ordinary hard disk.
著者Liu Q, Cheng JF, Li ZG, Lui JCS
期刊名稱IEEE Transactions on Knowledge and Data Engineering
詳細描述 This journal was considered as a tier-A journal as classified by the external visiting committee in FoE in 2011.
頁次2230 - 2245
關鍵詞disk-based computing; Graph computation; vertex-centric streamlined processing
Web of Science 學科類別Computer Science; Computer Science, Artificial Intelligence; Computer Science, Information Systems; Engineering; Engineering, Electrical & Electronic

上次更新時間 2021-26-02 於 02:10