The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Un problème d’énumération de triangles est l’un des problèmes fondamentaux des données graphiques. Bien que plusieurs algorithmes d’énumération de triangles basés sur MapReduce aient été proposés, ils souffrent encore de générer beaucoup de données intermédiaires. Dans cet article, nous proposons les algorithmes efficaces MapReduce pour énumérer chaque triangle du graphe massif sur la base d'une partition de sommets. Puisqu’un triangle est composé d’une arête et d’un coin, nos algorithmes vérifient l’existence d’une arête reliant les nœuds d’extrémité de chaque coin. Pour générer chaque triangle à partir d'un graphique en parallèle, nous divisons d'abord un graphique en plusieurs partitions de sommets et regroupons les arêtes et les coins du graphique pour chaque paire de partitions de sommets. Ensuite, on forme les triangles apparaissant dans chaque groupe. De plus, pour améliorer les performances de notre algorithme, nous supprimons les coins dupliqués existant dans plusieurs groupes. Notre évaluation expérimentale montre que les performances de notre algorithme proposé sont meilleures que celles de l'algorithme de pointe dans divers environnements.
Hongyeon KIM
Korea Univ. of Tech. & Edu.
Jun-Ki MIN
Korea Univ. of Tech. & Edu.
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.
Copier
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
Copier
@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},}
Copier
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 -