Parallelization of Extracting Connected Subgraphs with Common Itemsets in Distributed Memory Environments

DOI Web Site 1 Citations 13 References Open Access
  • Okuno Shingo
    Graduate School of Informatics, Kyoto University
  • Hiraishi Tasuku
    Academic Center for Computing and Media Studies, Kyoto University
  • Nakashima Hiroshi
    Academic Center for Computing and Media Studies, Kyoto University
  • Yasugi Masahiro
    Department of Artificial Intelligence, Kyushu Institute of Technology
  • Sese Jun
    National Institute of Advanced Industrial Science and Technology

Bibliographic Information

Published
2017
Resource Type
journal article
DOI
  • 10.2197/ipsjjip.25.256
Publisher
Information Processing Society of Japan

Description

<p>This paper proposes a parallel implementation of graph mining that extracts all connected subgraphs with common itemsets, of which the size is not less than a given threshold, from a graph and from itemsets associated with vertices of the graph, in distributed memory environments using the task-parallel language Tascell. With regard to this problem, we have already proposed parallelization of a backtrack search algorithm named COPINE and its implementation in shared memory environments. In this implementation, all workers share a single table, which is controlled by locks, that contains the knowledge acquired during the search to obviate the need for unnecessary searching. This sharing method is not practical in distributed memory environments because it would lead to a drastic increase in the cost of internode communications. Therefore, we implemented a sharing method in which each computing node has a table and sends its updates to the other nodes at regular time intervals. In addition to this, the high task creation cost for COPINE is problematic and thus the conventional work-stealing strategy in Tascell, which aims to minimize the number of internode work-steals, significantly degrades the performance since it increases the number of intranode work-steals for small tasks. We solved this problem by promoting workers to enable them to request tasks from external nodes. We also employed a work-stealing strategy based on estimation of the sizes of tasks created by victim workers. This approach enabled us to achieve good speedup performance with up to 8 nodes × 16 workers.</p>

Journal

Citations (1)*help

See more

References(13)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top