Aceleración de consultas en BD de grafos mediante el uso de operaciones de álgebra lineal.

Abstract

Las denominadas bases de datos de grafos (BDG) permiten consultar y almacenar información estructurada en grafos. En los últimos años estos sistemas han ganado popularidad y madurez, permitiendo gestionar grafos de gran tamaño y con tiempos de cómputo cada vez menores. De todas formas, el procesamiento eficiente de consultas sobre grafos sigue siendo un tema relevante en la industria y la academia. Una línea promisoria en este aspecto es transformarlas consultas sobre BDG en operaciones de álgebra lineal numérica (ALN) y,de esta forma, valerse del amplio conjunto de herramientas que ofrece dicho campo. Adicionalmente, el uso de operaciones de ALN posiciona a las GPUs(del inglés Graphics Processing Units), como una alternativa eficiente y de bajo costo para desarrollar tareas vinculadas al procesamiento y optimización de consultas sobre grafos, en particular SPARQL (SPARQL Protocol And RDF Query Language) el lenguaje de consulta estándar sobre grafos en RDF (Resource Description Framework).Representar grafos relevantes (como los que modelan redes sociales) con matrices tiene la particularidad de que, en general, genera matrices con muchos coeficientes sin información. Mapearlas de forma directa entonces no es una buena opci ́on, ya que se desperdicia mucha memoria en datos que no son relevantes y el cómputo de las operaciones implica trabajo innecesario. Esta situación motiva el uso de matrices dispersas. En este trabajo se estudia la composición de operaciones de ALN que resuelven consultas utilizando una matriz para representar el grafo que modela la base de datos y se realiza un prototipo utilizando C++ y CUDA.Se busca entonces la mejor forma de cargar y operar con las matrices, para esto se compararon distintos formatos de almacenamiento resultando el de mejor performance respecto a nuestros intereses el denominado CSR (Compressed Storage Row).Para realizar las pruebas se utilizan conjuntos de datos generados deBer-lin SPARQL Benchmark. Estos datos deben ser transformados al formato de entrada que utiliza el prototipo, para esto se implementa un traductor utilizando Java. Luego de realizado el prototipo, se ejecutan pruebas en él y en otras implementaciones de motores de bases de datos RDF los resultados fueron comparados mostrando que existen ventajas al utilizar la GPU para consultas cuyo grafo resultado es grande.