DC Field | Value | Language |
---|---|---|
dc.contributor.author | Jinha Kim | - |
dc.contributor.author | Han, W.-S | - |
dc.contributor.author | Sangyeon Lee | - |
dc.contributor.author | Kyungyeol Park | - |
dc.contributor.author | Hwanjo Yu | - |
dc.date.accessioned | 2016-04-01T07:35:45Z | - |
dc.date.available | 2016-04-01T07:35:45Z | - |
dc.date.created | 2017-02-13 | - |
dc.date.issued | 2014-06 | - |
dc.identifier.issn | 0730-8078 | - |
dc.identifier.other | 2014-OAK-0000028837 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/26671 | - |
dc.description.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 :1/0 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-ofthe-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. | - |
dc.description.statementofresponsibility | ungraded | - |
dc.language | English | - |
dc.publisher | ACM SIGMOD | - |
dc.relation.isPartOf | Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data | - |
dc.title | OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs | - |
dc.type | Article | - |
dc.contributor.college | 창의IT융합공학과 | - |
dc.identifier.doi | 10.1145/2588555.2588563 | - |
dc.author.google | Kim J., Han W.-S., Lee S., Park K., Yu H. | - |
dc.relation.startpage | 637 | - |
dc.relation.lastpage | 648 | - |
dc.contributor.id | 10056897 | - |
dc.relation.journal | Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data | - |
dc.relation.sci | SCI | - |
dc.collections.name | Journal Papers | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pp.637 - 648 | - |
dc.identifier.wosid | 000454714600057 | - |
dc.citation.endPage | 648 | - |
dc.citation.startPage | 637 | - |
dc.citation.title | Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data | - |
dc.contributor.affiliatedAuthor | Han, W.-S | - |
dc.identifier.scopusid | 2-s2.0-84904369672 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.scptc | 21 | * |
dc.date.scptcdate | 2018-05-121 | * |
dc.type.docType | Proceedings Paper | - |
dc.subject.keywordAuthor | Triangulation | - |
dc.subject.keywordAuthor | Big data | - |
dc.subject.keywordAuthor | Parallel processing | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Information Systems | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Computer Science | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.