Exploitation de la structure en communautés pour la réduction de défauts de cache dans la fouille des réseaux sociaux

Thomas Messi Nguélé (1, 2) , Maurice Tchuenté (3, 2) , Jean-François Mehaut (2, 1)

1 CORSE - Compiler Optimization and Run-time Systems
2 LIRIMA - Laboratoire International de Recherche en Informatique et Mathématiques Appliquées
3 UY1 - Université de Yaoundé I

One of social graphs property is the community structure. When executing on graphs, most social network mining algorithms make reference to the neighborhood of the current treated node, to nodes situated to its community. Can we reduce the execution time of social graph algorithm if we take into account the community structure of graph in the data structure used in the runtime? The goal of such a data structure is to reduce cache misses, which will reduce execution time. In this paper, we present a data structure responding to this goal. A comparaison between this data structure with those used in graph analysis DSLs and platforms (Yale representation, adjacency list or bloc) shows that taking into account this property contribute to reduce cache misses (until 20%) and to reduce execution time (until 14%) of social network mining programms.

L’une des propriétés des graphes sociaux est leur structure en communautés. La plupart des algorithmes de fouille des réseaux sociaux s’exécutent sur les nœuds du graphe en faisant référence aux nœuds situés dans le voisinage du nœud en cours d’exécution, aux nœuds situés dans sa communauté. Peut-on réduire le temps d’exécution des algorithmes des graphes sociaux si l’on tient compte, dans la structure de données utilisée dans l’environnement d’exécution, de l’organisation en communauté des nœuds du graphe? L’objectif d’une telle structure est de réduire le nombre de défauts de cache, ce qui a pour effet de réduire le temps d’exécution. Dans cet article, nous présentons une structure de données répondant à cet objectif. Une comparaison avec celles utilisées dans les DSLs et les plates-formes d’analyse de graphes (représentation de Yale, représentation par liste ou bloc d’adjacence) montre que la prise en compte de cette propriété permet de réduire les défauts de cache (jusqu’à 20%) et de réduire le temps d’exécution (jusqu’à 14%) des programmes de fouille des réseaux sociaux.

Mots clés: Cache management; data structure; runtime.

Mots clés: Gestion du cache; structure de données; environnement d’exécution

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Thomas Messi Nguélé, Maurice Tchuenté, Jean-François Mehaut. Exploitation de la structure en communautés pour la réduction de défauts de cache dans la fouille des réseaux sociaux. Conférence de Recherche en Informatique (CRI), Dec 2015, Yaoundé, Cameroun. ⟨hal-01252798⟩