A Parallel Maximal Matching Algorithm for Large Graphs Using Pregel
- Authors
- Lim, Byungnam; Chung, Yon Dohn
- Issue Date
- 7월-2014
- Publisher
- IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
- Keywords
- matching; parallel matching; Pregel
- Citation
- IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, v.E97D, no.7, pp.1910 - 1913
- Indexed
- SCIE
SCOPUS
- Journal Title
- IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
- Volume
- E97D
- Number
- 7
- Start Page
- 1910
- End Page
- 1913
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/98035
- DOI
- 10.1587/transinf.E97.D.1910
- ISSN
- 1745-1361
- Abstract
- Graph matching is to find an independent edge set in a graph. It can be used for various purposes such as finding a cover in a graph, chemical structural computations, multi-level graph partitioning and so on. When a graph is too large to be handled by a single machine, we should use multiple machines. In this paper, we use Pregel, a cloud graph processing architecture which is able to process massive scale graph data in scalable and fault-tolerant ways. We propose a parallel maximal matching algorithm described in the Pregel's vertex-centric BSP model. We test our algorithm on an 8 node cluster and the results show that our algorithm can realize high quality matching for a large graph in a short time. Also, our algorithm is linearly scalable with the number of machines.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - Graduate School > Department of Computer Science and Engineering > 1. Journal Articles
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.