Estructuras compactas dinámicas más eficientes para bases de datos de grafos con atributos

Abstract

Los grafos son estructuras de datos muy útiles ya que permiten guardar conexiones entre entidades que comparten alguna relación. A veces estas estructuras se extienden para poder guardar información en sus nodos y aristas, a esta variante se le conoce como grafos con atributos. Debido a la importancia de los grafos con atributos, existen varios motores de bases de datos que buscan guardar estas estructuras de forma compacta incluyendo operaciones que permiten consultar la base de datos de forma eficiente. Pero guardar la base de datos y consultarla no es lo único que deben satisfacer los motores, además deben permitir dinamismo en sus estructuras, es decir la capacidad de cambiar la información que representan. Es por esto que existen motores de bases de datos que basan su implementación en estructuras de datos que no solo son compactas, si no que además son dinámicas. En este trabajo se estudia el motor de base de datos Attk2DynTree. Este motor basa su implementación en una estructura de datos sucinta y dinámica llamada k 2 -tree. Esta estructura permite comprimir la matriz de adyacencia dividiendo la matriz en sub matrices más pequeñas y guardando solo aquellas que contienen información. Debido a lo anterior, los k 2 -trees suelen ser bastante eficientes ya que, en la práctica los grafos suelen ser esparsos y con subconjuntos de elementos densamente conectados. Actualmente existen k 2 -trees más eficientes que los que actualmente posee Attk2DynTree. Lo que se busca con este trabajo es elegir el mejor de ellos y reemplazar el antiguo k 2 - tree que hay en Attk2DynTree con uno más eficiente y de esta forma presentar una nueva versión de Attk2DynTree. Para lograr lo anterior, se divide el trabajo total en tres grandes hitos. El primero consiste en implementar la operación de borrado de aristas, para un k 2 -tree desarrollado recientemente. En esta parte del trabajo se muestra que la nueva operación tiene una complejidad de tiempo igual al resto de operaciones. En el segundo hito se comparan cuatro implementaciones de k 2 -trees, en una serie de pruebas que intentan medir el tiempo que demoran sus operaciones y la memoria que ocupan. Al final de esta sección se elige un k 2 -tree candidato para ser incorporado en la nueva versión de Attk2DynTree. En el último hito, se integra el nuevo k 2 -tree en Attk2DynTree, y se ponen a prueba las dos versiones usando grafos reales de ratings de películas. Finalmente, se concluye que la nueva versión de Attk2DynTree es mucho más rápida que la versión antigua en las operaciones que involucran a los k 2 -trees, se obtienen tiempos de inserción hasta 20 veces más rápidos y consultas de búsqueda hasta 3 veces más rápidas, ocupando un 28 % de memoria extra.