conclusiones.tex

\chapter{CONCLUSIONES}\label{chap:conclusion}
\vskip 3.0ex

%\textcolor{red}{En proceso...}

En este trabajo se desarrolla un método de compresión de grafos no dirigidos y poco densos, basado en clustering de cliques maximales, usando estructuras de datos sucintos. Se logra llegar a una representación comprimida que permite responder consultas usuales como listado de vecinos de un nodo y reconstrucción del grafo, y otras consultas novedosas como obtener el listado de cliques maximales o saber si dos nodos son vecinos, todo sin tener que descomprimir el grafo.

El nivel de compresión, medido en BPE, es bastante competitivo al estado del arte, siendo superado solo por las dos versiones evaluadas de k2tree, ambas contando con una reciente mejora realizada directamente por la autora para representar grafos no dirigidos. Comparado con los otros algoritmos, el resultado en compresión es bastante mejor, sobre todo comparado con WebGraph. Los mejores BPE se logran con los grafos \texttt{coPapersDBLP} (0,78) y \texttt{coPapersCiteseer} (0,52), los cuales presentan los índices de clusterización más altos, muy pocos cliques comparado con la cantidad de nodos, y la mayoría de dichos cliques con al menos 100 nodos.
%superando en todos los casos estudiados a los otros algoritmos. Incluso puntualmente para el caso de los grafos \texttt{coPapersDBLP} y \texttt{coPapersCiteseer}, los cuales poseen los coeficiente de clusterización (0,80 y 0,83) y transitividad (0,65 y 0,77) más altos (ver Tabla~\ref{table:gafros3}, se logran los BPE de 0,80 y 0,52 respectivamente, lo que es muy eficiente. Si bien este resultado en la compresión es muy positivo, es necesario reconocer el efecto que conlleva en los tiempos de acceso 

Para el tiempo de acceso aleatorio, medido como los segundos por arco que toma recuperar vecinos para un millón de nodos, en varios casos se logran mejores resultados que ambos algoritmos de k2tree, pero no logra superar a BFS ni menos a WebGraph, que mantiene total predominancia en este ámbito. Analizando junto al resultado en BPE, se puede apreciar que la propuesta se mantiene competitiva, siempre en la zona media de la comparación. El mejor balance lo logran los grafos \texttt{marknewman-condmat}, \texttt{dblp-2010}, \texttt{dblp-2011}, y \texttt{snap-dblp}, todos los cuales poseen una cantidad similar entre vértices y cliques maximales. %Mención especial \texttt{snap-amazon}, que contiene más del doble de cliques que vértices, y también logra un buen balance.
%Comparando los tiempos de acceso aleatorio de la propuesta entre los grafos, e igual que para los BPE, también se logran para \texttt{coPapersDBLP} (1,51 $[\mu s]$) y \texttt{coPapersCiteseer} (1,30 $[\mu s]$). Ambos casos están entre la mayor cantidad de vértices por particiones, y la menor cantidad de bytes por particiones.

Para el tiempo de reconstrucción secuencial del grafo, la estructura propuesta presenta su menor desempeño. En todos los casos, alguna versión de k2tree logra una respuesta más rápida, del orden de 4 veces mejor. Se destaca que para los grafos \texttt{marknewman-astro}, \texttt{marknewman-condmat} y \texttt{dblp-2010}, el método logra mejor tiempo que WebGraph.

En cuanto al tiempo de recuperar el listado de cliques maximales, la propuesta es mucho mas rápida que el algoritmo \textbf{Quick Cliques}\footnote{\url{https://github.com/darrenstrash/quick-cliques}} y si bien es cierto que para generar la estructura se debe generar dicho listado previamente, una vez comprimido el grafo se puede volver a obtener en un tiempo menor. Especial atención a los grafos \texttt{coPapersDBLP} y \texttt{coPapersCiteseer}, que son los grafos con menor BPE, y recuperan el listado de cliques más de 10 veces más rápido.

Esta propuesta además posee la consulta que permite saber si dos vértices son vecinos, sin tener que generar los listados de adyacencia de ninguno de los dos, directamente de la estructura, y en un tiempo  $O((M_{1} + M_{2}) \cdot bpu_{p})$ cuando hay bytes en las particiones, o $O(M_{1} + M_{2})$ si no los hay, siendo $M_{1}$ la cantidad de particiones que contienen al vértice 1, y $M_{2}$ al vértice 2. 

Con esto en consideración, una buena aplicación para el método propuesto son máquinas donde el espacio para guardar el grafo sea limitado, como dispositivos móviles con poca RAM y espacio en disco, donde se pueden almacenar los grafos gracias al buen nivel de compresión, y además permite responder consultas sin ocupar espacio en la descompresión, pagando un tiempo algo mayor.

Como trabajo futuro, se puede explorar cómo mejorar los tiempos de acceso de esta estructura, por ejemplo investigar nuevas funciones de ranking en la heurística de clusterización. Otra opción es explotar el potencial de paralelismo que posee la estructura compacta, ya que cada partición se puede acceder de manera simultánea, y cada comparación de bytes dentro de las particiones se puede optimizar usando instrucciones paralelas como SIMD\footnote{SIMD: Single Instruction, Multiple Data. Una Instrucción, múltiples datos.}.