Paper Info
Title
OPT: a new framework for overlapped and parallel triangulation in large-scale graphs
Abstract
Graph triangulation, which finds all triangles in a graph, has been actively studied due to its wide range of applications in the network analysis and data mining. With the rapid growth of graph data size, disk-based triangulation methods are in demand but little researched. To handle a large-scale graph which does not fit in memory, we must iteratively load small parts of the graph. In the existing literature, achieving the ideal cost has been considered to be impossible for billion-scale graphs due to the memory size constraint. In this paper, we propose an overlapped and parallel disk-based triangulation framework for billion-scale graphs, OPT, which achieves the ideal cost by (1) full overlap of the CPU and I/O operations and (2) full parallelism of multi-core CPU and FlashSSD I/O. In OPT, triangles in memory are called the internal triangles while triangles constituting vertices in memory and vertices in external memory are called the external triangles. At the macro level, OPT overlaps the internal triangulation and the external triangulation, while it overlaps the CPU and I/O operations at the micro level. Thereby, the cost of OPT is close to the ideal cost. Moreover, OPT instantiates both vertex-iterator and edge-iterator models and benefits from multi-thread parallelism on both types of triangulation. Extensive experiments conducted on large-scale datasets showed that (1) OPT achieved the elapsed time close to that of the ideal method with less than 7% of overhead under the limited memory budget, (2) OPT achieved linear speed-up with an increasing number of CPU cores, (3) OPT outperforms the state-of-the-art parallel method by up to an order of magnitude with 6 CPU cores, and (4) for the first time in the literature, the triangulation results are reported for a billion-vertex scale real-world graph.
Year
DOI
Venue
2014
10.1145/2588555.2588563
SIGMOD Conference
Keywords
Field
DocType
big data,parallel processing,search process,triangulation
Central processing unit,Minimum-weight triangulation,Vertex (geometry),Computer science,Algorithm,Triangulation (social science),Network analysis,Multi-core processor,Delaunay triangulation,Auxiliary memory
Conference
Citations 
PageRank 
References 
24
0.69
22
Authors
5
Name
Order
Citations
PageRank
Jin-ha Kim132918.78
Wook-Shin Han280557.85
Sangyeon Lee31333.82
Kyungyeol Park41313.46
Hwanjo Yu51715114.02