Presence of triangles in massive graphs provides many important indications to different graph algorithms. In-memory algorithms don't work for massive graphs since these graphs cannot fit into the memory. Recently, external memory-based algorithms have been proposed for efficient triangle listing which focused on I/O efficiency to improve the performance of triangle listing. However, the existing studies still suffer from tremendous calculations result from involving lot of I/Os and joining operations between adjacency lists. This paper focuses on the efficient technique for joining adjacency lists to output triangles by exploiting the CPU parallelism. We first present the new notions of summarized bit batch vector to represent the adjacency lists of massive graphs. We then propose a parallel triangle listing algorithm that asynchronously access the indexed summarized data and join them in groups. We experimentally show that our proposed technique outperforms the existing solutions significantly.
展开▼
