Efficient Triangulation in Massaive Graphs
Md Mostofa Kamal Rasel
Massive Graph Triangle Listing Graph Indexing I/O-efficient Algorithm CPU Parallelism Bit Vector Compressed Bit Vector;
- 원문 URL
Triangle listing is a basic operator in dealing with many graph problems. In-memory algorithms don't work well in recent massive graphs such as social networks since these graphs cannot fit into the memory. Thus recently external memory based algorithms have been proposed. However, the existing studies still suffer from frequent multiple scans of the whole graph on the disk and tremendous calculation coming from involving the whole graph in every iteration. This paper presents a novel index-based method for listing triangles in massive graphs. We first present the new notions of vertex range index and potential cone vertex index. Then we propose an index join based triangle listing algorithm. We access indexed data asynchronously and join them to list triangles using a multi-threaded parallel processing technique. We experimentally show that index join based triangulation algorithm outperforms the state-of-the-art solution by 3 to 8 times in terms of wall clock time. We devise another different triangulation algorithm based on summarized bit batch vector that utilizes the hardware properties for joining two adjacency lists. This summarized bit batch vector algorithm outperforms MGT by more than an order of magnitude and index join based algorithm by 2 times.