IEICE TRANSACTIONS on Information
An Efficient Parallel Triangle Enumeration on the MapReduce Framework
Summary :
A triangle enumerating problem is one of fundamental problems of graph data. Although several triangle enumerating algorithms based on MapReduce have been proposed, they still suffer from generating a lot of intermediate data. In this paper, we propose the efficient MapReduce algorithms to enumerate every triangle in the massive graph based on a vertex partition. Since a triangle is composed of an edge and a wedge, our algorithms check the existence of an edge connecting the end-nodes of each wedge. To generate every triangle from a graph in parallel, we first split a graph into several vertex partitions and group the edges and wedges in the graph for each pair of vertex partitions. Then, we form the triangles appearing in each group. Furthermore, to enhance the performance of our algorithm, we remove the duplicated wedges existing in several groups. Our experimental evaluation shows the performance of our proposed algorithm is better than that of the state-of-the-art algorithm in diverse environments.
- Publication
- IEICE TRANSACTIONS on Information Vol.E102-D No.10 pp.1902-1915
- Publication Date
- 2019/10/01
- Publicized
- 2019/07/11
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2018EDP7421
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Hongyeon KIM
Korea Univ. of Tech. & Edu.
Jun-Ki MIN
Korea Univ. of Tech. & Edu.
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hongyeon KIM, Jun-Ki MIN, "An Efficient Parallel Triangle Enumeration on the MapReduce Framework" in IEICE TRANSACTIONS on Information,
vol. E102-D, no. 10, pp. 1902-1915, October 2019, doi: 10.1587/transinf.2018EDP7421.
Abstract: A triangle enumerating problem is one of fundamental problems of graph data. Although several triangle enumerating algorithms based on MapReduce have been proposed, they still suffer from generating a lot of intermediate data. In this paper, we propose the efficient MapReduce algorithms to enumerate every triangle in the massive graph based on a vertex partition. Since a triangle is composed of an edge and a wedge, our algorithms check the existence of an edge connecting the end-nodes of each wedge. To generate every triangle from a graph in parallel, we first split a graph into several vertex partitions and group the edges and wedges in the graph for each pair of vertex partitions. Then, we form the triangles appearing in each group. Furthermore, to enhance the performance of our algorithm, we remove the duplicated wedges existing in several groups. Our experimental evaluation shows the performance of our proposed algorithm is better than that of the state-of-the-art algorithm in diverse environments.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018EDP7421/_p
Copy
@ARTICLE{e102-d_10_1902,
author={Hongyeon KIM, Jun-Ki MIN, },
journal={IEICE TRANSACTIONS on Information},
title={An Efficient Parallel Triangle Enumeration on the MapReduce Framework},
year={2019},
volume={E102-D},
number={10},
pages={1902-1915},
abstract={A triangle enumerating problem is one of fundamental problems of graph data. Although several triangle enumerating algorithms based on MapReduce have been proposed, they still suffer from generating a lot of intermediate data. In this paper, we propose the efficient MapReduce algorithms to enumerate every triangle in the massive graph based on a vertex partition. Since a triangle is composed of an edge and a wedge, our algorithms check the existence of an edge connecting the end-nodes of each wedge. To generate every triangle from a graph in parallel, we first split a graph into several vertex partitions and group the edges and wedges in the graph for each pair of vertex partitions. Then, we form the triangles appearing in each group. Furthermore, to enhance the performance of our algorithm, we remove the duplicated wedges existing in several groups. Our experimental evaluation shows the performance of our proposed algorithm is better than that of the state-of-the-art algorithm in diverse environments.},
keywords={},
doi={10.1587/transinf.2018EDP7421},
ISSN={1745-1361},
month={October},}
Copy
TY - JOUR
TI - An Efficient Parallel Triangle Enumeration on the MapReduce Framework
T2 - IEICE TRANSACTIONS on Information
SP - 1902
EP - 1915
AU - Hongyeon KIM
AU - Jun-Ki MIN
PY - 2019
DO - 10.1587/transinf.2018EDP7421
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2019
AB - A triangle enumerating problem is one of fundamental problems of graph data. Although several triangle enumerating algorithms based on MapReduce have been proposed, they still suffer from generating a lot of intermediate data. In this paper, we propose the efficient MapReduce algorithms to enumerate every triangle in the massive graph based on a vertex partition. Since a triangle is composed of an edge and a wedge, our algorithms check the existence of an edge connecting the end-nodes of each wedge. To generate every triangle from a graph in parallel, we first split a graph into several vertex partitions and group the edges and wedges in the graph for each pair of vertex partitions. Then, we form the triangles appearing in each group. Furthermore, to enhance the performance of our algorithm, we remove the duplicated wedges existing in several groups. Our experimental evaluation shows the performance of our proposed algorithm is better than that of the state-of-the-art algorithm in diverse environments.
ER -
English
