Introducción al Trabajo de Título
Entrar

Generalized Hypertree Decompositions sobre el Ring Memoria 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, Análisis y diseño de algoritmos y estructuras de datos

Descripción


El Ring es una nueva estructura compacta que permite resolver basic graph patterns (subgraph matching) en bases de datos de grafos; ésta es la consulta fundamental soportada en SPARQL, por ejemplo. El Ring soporta el algoritmo Leapfrog TrieJoin (LTJ), que es worst-case optimal (wco). Un algoritmo más potente es separar la consulta en componentes cíclicas, de modo que quede como un árbol de componentes, resolver cada componente con un algoritmo wco, y luego usar un algoritmo de Yannakakis para resolver la query resultante en forma instance-optimal, que es mejor que worst-case-optimal. 

La tesis consiste en usar el Ring como estructura para resolver las componentes, y luego estudiar una forma conveniente de representar los resultados en forma de Ring nuevamente para ejecutar Yannakakis. Es de esperar que esto nos de una forma compacta de representar los resultados intermedios, con la que se pueda ejecutar la query de forma eficiente. Puede llevar a una publicación si los resultados son buenos.