Introducción al Trabajo de Título
Entrar

Analítica de grafos usando estructuras compactas Doble Titulación Ciencia e Ingeniería de datos Teoría de la computación

Profesor Guia
Sub Áreas Bases de datos, Procesamiento masivo de datos, Web semántica, Análisis y diseño de algoritmos y estructuras de datos

Descripción


El Ring es una estructura compacta que, usando un 5% del espacio de las estructuras clásicas, puede resolver multijoins en tiempos similares, y siendo worst-case-optimal, una propiedad teórica muy apreciada. En esta memoria larga se plantea utilizarlo para tareas de analítica de grafos, en particular para queries donde algunas variables no nos interesan, sino que queremos contar cuántas soluciones hay para cada combinación de las variables no mudas (ej. se puede querer contar el número de triángulos en el grafo). El Ring tiene capacidad, en algunos casos, de trabajar sobre rangos de valores de una sola vez. Se plantea estudiar la forma de que resuelva estas consultas más rápidamente que enumerando una a una todas las soluciones (y comparar contra este baseline). Puede llevar a una publicación si los resultados son buenos.