Titre: Compression de graphiques À l’aide de Techniques de correspondance de motifs

Auteurs: Rushabh Jitendrakumar Shah

Télécharger le PDF

Résumé: Les graphiques peuvent être utilisés pour représenter une grande variété de données appartenant à différents domaines. Les graphiques peuvent capturer la relation entre les données de manière efficace et ont été largement utilisés. Ces derniers temps, avec l’avènement du Big Data, il a été nécessaire de stocker et de calculer efficacement de grands ensembles de données. Cependant, compte tenu de la taille des ensembles de données en question, trouver des méthodes optimales pour extraire et traiter les données a été un défi. Par conséquent, dans cet article, nous étudions différentes techniques de compression de graphes et proposons de nouveaux algorithmes pour faire de même. Plus précisément, étant donné un graphe G =(V, E), où V est l’ensemble des sommets et E est l’ensemble des arêtes, et |V|= n, nous proposons des techniques pour compresser la représentation matricielle d’adjacence du graphe. Nos algorithmes sont basés sur la recherche de motifs dans les données de la matrice d’adjacence et sur le remplacement des motifs communs par des marqueurs spécifiques. Toutes les techniques proposées ici sontcompression sans perte de graphiques. Sur la base des résultats expérimentaux, il est observé que nos techniques proposées atteignent près de 70% de compression par rapport à la représentation matricielle d’adjacence. Les résultats montrent que les grands graphes peuvent être stockés efficacement dans une mémoire plus petite et exploiter la puissance de traitement parallèle des nœuds de calcul ainsi que transférer efficacement les données entre les ressources.