La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

An Efficient Parallel Triangle Enumeration on the MapReduce Framework Une énumération efficace de triangles parallèles sur le framework MapReduce

Hongyeon KIM, Jun-Ki MIN

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Information Vol.E102-D No.10 pp.1902-1915
Date de publication
2019/10/01
Publicisé
2019/07/11
ISSN en ligne
1745-1361
DOI
10.1587/transinf.2018EDP7421
Type de manuscrit
PAPER
Catégories
Fondamentaux des Systèmes d'Information

Auteurs

Hongyeon KIM
  Korea Univ. of Tech. & Edu.
Jun-Ki MIN
  Korea Univ. of Tech. & Edu.

Mots-clés

Table des matières