COMPRESIÓN DE DIGRAFOS BASADA EN METODOLOGÍAS DE RENUMERACIÓN DE VÉRTICES

Abstract

El presente trabajo muestra un estudio sobre cómo el uso de metodologías para la renumeracióny reordenamiento de vértices puede afectar y mejorar la tasa de compresiónutilizando algoritmos de compresión basados en índices invertidos sobre grafos dirigidos.Estos algoritmos no están diseñados inicialmente para este contexto, por lo que sebusca una comparación entre estos y las herramientas actuales creadas específicamentepara comprimir estas estructuras de datos. También tienen la capacidad de descomprimircientos de miles de nodos por segundo, lo cual hace que sean buenos candidatos paracomparar. El objetivo será analizar las tasas de compresión utilizando para eso el grafoescrito por listas de adyacencia escritas en orden por grado de salida, entrada, comunidadescon grado de salida, comunidades con grado de entrada y aleatorio para contrastarla importancia del orden de los nodos. A su vez se medirá el tiempo que demora el comprimircomo descomprimir los archivos binarios obtenidos.

This work shows a study about how the use of renumbering and reordering methodologiesover vértices can impact and improve the compression rate using compressionalgorithms based on inverted index over directed graphs. These algorithms are notinitially designed for this context, thus it seeks to compare this with updated tools createdspecifically to compress this data structure. The inverted index compression algorithmshave the ability to decompress hundreds of thousands of nodes per second, and this makes them good candidates to compare. The objective will be to analyze the compression rates using out-degree order, in-degree order, community with out-degree order, community with in-degree order and a no order to contrast them. Also, the time that will take to compress and decompress will be measured.