Open Access System for Information Sharing

Login Library

 

Article
Cited 31 time in webofscience Cited 40 time in scopus
Metadata Downloads
Full metadata record
Files in This Item:
There are no files associated with this item.
DC FieldValueLanguage
dc.contributor.authorJinha Kim-
dc.contributor.authorHan, W.-S-
dc.contributor.authorSangyeon Lee-
dc.contributor.authorKyungyeol Park-
dc.contributor.authorHwanjo Yu-
dc.date.accessioned2016-04-01T07:35:45Z-
dc.date.available2016-04-01T07:35:45Z-
dc.date.created2017-02-13-
dc.date.issued2014-06-
dc.identifier.issn0730-8078-
dc.identifier.other2014-OAK-0000028837-
dc.identifier.urihttps://oasis.postech.ac.kr/handle/2014.oak/26671-
dc.description.abstractGraph 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.statementofresponsibilityungraded-
dc.languageEnglish-
dc.publisherACM SIGMOD-
dc.relation.isPartOfProceedings of the 2014 ACM SIGMOD International Conference on Management of Data-
dc.titleOPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs-
dc.typeArticle-
dc.contributor.college창의IT융합공학과-
dc.identifier.doi10.1145/2588555.2588563-
dc.author.googleKim J., Han W.-S., Lee S., Park K., Yu H.-
dc.relation.startpage637-
dc.relation.lastpage648-
dc.contributor.id10056897-
dc.relation.journalProceedings of the 2014 ACM SIGMOD International Conference on Management of Data-
dc.relation.sciSCI-
dc.collections.nameJournal Papers-
dc.type.rimsART-
dc.identifier.bibliographicCitationProceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pp.637 - 648-
dc.identifier.wosid000454714600057-
dc.citation.endPage648-
dc.citation.startPage637-
dc.citation.titleProceedings of the 2014 ACM SIGMOD International Conference on Management of Data-
dc.contributor.affiliatedAuthorHan, W.-S-
dc.identifier.scopusid2-s2.0-84904369672-
dc.description.journalClass1-
dc.description.journalClass1-
dc.description.scptc21*
dc.date.scptcdate2018-05-121*
dc.type.docTypeProceedings Paper-
dc.subject.keywordAuthorTriangulation-
dc.subject.keywordAuthorBig data-
dc.subject.keywordAuthorParallel processing-
dc.relation.journalWebOfScienceCategoryComputer Science, Information Systems-
dc.description.journalRegisteredClassscie-
dc.description.journalRegisteredClassscopus-
dc.relation.journalResearchAreaComputer Science-

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher

한욱신HAN, WOOK SHIN
Grad. School of AI
Read more

Views & Downloads

Browse