Implementación de operaciones binarias y de consulta sobre un k2-tree

Abstract

En la actualidad la web se expande prácticamente de forma descontrolada, por lo que su tamaño y alcance es cada vez más difícil de cuantificar. Algunos análisis del comportamiento de la web necesitan almacenar información sobre la existencia de un vínculo entre una página y otra. De forma natural, surge la idea de representar dichos vínculos a través de líneas o aristas; es por esto que se utilizan grafos. Es difícil dimensionar el tamaño de un grafo web que represente todas conexiones de todas las páginas existentes, más aún imaginar esa información almacenada en algún lugar. Lo lógico sería buscar la forma de reducir el tamaño de los archivos donde se almacenen, como por ejemplo comprimiendo esta información, pero conservando la funcionalidad de la estructura de datos original. El k2-tree representa de forma compacta la matriz de adyacencia de un grafo web dejando fuera las grandes áreas vacías (donde no existe ninguna conexión). Al dejar de lado estas áreas no se pierde la capacidad de navegación a través de los nodos. Sobre las matrices de adyacencia es posible realizar operaciones binarias como lo son el complemento, la diferencia, la unión y la intersección. La finalidad de este proyecto en particular es implementar estas mismas operaciones sobre k2-tree, para luego confrontar la implementación original y la comprimida en términos de desempeño, tiempo de respuesta, entre otros.