Compact and efficient representations of graphs
Sandra Álvarez García · Dialnet (Universidad de la Rioja) · 2014
En esta tesis estudiamos el problema de la creacion de representaciones compactas y eficientes de grafos. Proponemos nuevas estructuras para persistir y consultar grafos de diferentes dominios, prestando especial atencion al diseno de soluciones eficientes para grafos generales y grafos RDF. Hemos disenado una nueva herramienta para generar grafos a partir de fuentes de datos heterogeneas mediante un sistema de definicion de reglas. Es una herramienta de proposito general y, hasta nuestro conocimiento, no existe otra herramienta de estas caracteristicas en el Estado del Arte. Otra contribucion de este trabajo es una representacion compacta de grafos generales, que soporta el acceso eficiente a los atributos y aristas del grafo. Asi mismo, hemos estudiado el problema de la distribucion de grafos en un entorno paralelo, almacenados sobre estructuras compactas, y hemos propuesto nueve alternativas diferentes que han sido evaluadas experimentalmente. Tambien hemos propuesto un nuevo indice para RDF que soporta la resolucion basica de SPARQL de forma comprimida. Por ultimo, presentamos una nueva estructura compacta para almacenar relaciones ternarias cuyo diseno se enfoca a la representacion eficiente de datos RDF. Todas estas propuestas han sido experimentalmente validadas con conjuntos de datos ampliamente aceptados, obteniendose resultados competitivos comparadas con otras alternativas del Estado del Arte.