Multiplicación de matrices booleanas comprimidas mediante bicliques.
Loading...
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
La multiplicación booleana de matrices es una operación fundamental en numerosas aplicaciones basadas en grafos, como el análisis de redes web y sociales, la recuperación de información y la evaluación de consultas sobre grafos. No obstante, las representaciones dispersas convencionales, como CSR y CSC, siguen implicando cos tos significativos de espacio y tiempo cuando se aplican a grafos de gran escala. En este trabajo, hemos desarrollado una representación basada en bicliques que comprime matrices booleanas mediante su descomposición en subgrafos bipartitos densos, capturando así grandes conjuntos de aristas de manera implícita. En primer lugar, mejoramos el algoritmo iterativo de extracción de bicliques de Hernández y Navarro mediante la incorporación de una adaptación de parámetros basada en percentiles, la cual ajusta dinámicamente dichos parámetros según la distribución de grados, reduciendo el tiempo de cómputo de extracción y aumentando la tasa de compresión. Luego, extendemos el algoritmo de multiplicación de Schoor para operar directamente sobre matrices codificadas con bicliques, permitiendo una forma composicional de multiplicación en la que la salida también puede representarse como una colección de bicliques. Nuestros resultados experimentales demuestran que nuestro enfoque logra reducciones en espacio y tiempo de cómputo, alcanzando aceleraciones de hasta 200× en comparación con implementaciones basadas en CSR/CSC, y una competitiva cantidad de bits por arista comparado con el k2-tree. Estos resultados demuestran que la compresión basada en bicliques ofrece un equilibrio efectivo entre compresión y operatividad algebraica para el procesamiento de matrices booleanas a gran escala.
Description
Tesis presentada para optar al grado de Magíster en Ciencias de la Computación.
Keywords
Algoritmos computacionales, Teoría de grafos, Álgebra booleana