Alvaro Graves’s Weblog

Últimamente me ha tocado “jugar” bastante con grafos RDF de distintos tamaños (de unos pocos cientos de nodos y aristas hasta varios millones). Después de realizar análisis convencionales de éstos, tales como el grado promedio, el número de componentes, etc. me he encontrado con que en general no he visto buenas plataformas para manejar estos grafos.

Uno de los problemas principales es que -hasta donde tengo conocimiento- no existen buenas estructuras de datos para grafos en general (menos para RDF que es dirigido y considera aristas con etiquetas). En alguna parte leí que “la estructura de datos define el algoritmo”. En parte por esto quizás para hacer cualquier cosa más o menos “interesante” sea carísimo.

Como ejemplo de contraste, basta tomar el modelo relacional, el cual ha sido tremendamente exitoso y ampliamente usado desde hace 30 años en la academia e industria. Ha traves del uso de ingeniosas estructuras de datos, tales como B-Trees, R-Trees -sólo por mencionar algunas- es posible realizar operaciones en tiempo logarítmico, lineal, etc.

Sin embargo, cuando empezamos a hablar de grafos y realizar tareas más “interesantes”, no he logrado encontrar una buena plataforma para trabajar. Me explico: Si alguien ha trabajado con RDF/XML al poco tiempo se dará cuenta que no sólo es difícil de parsear, sino principalmente “poco natural” (el guardar un grafo en un árbol no es de las mejores ideas cuando se manejan muchísimos nodos).

Asimismo, el tratar de usar una base de datos, es decir, guardar el grafo en una (o más) tabla(s) hace que muchas búsquedas, como la ruta más corta entre 2 puntos, sea muy costosa.
Hasta el momento y siguiendo la filosofía UNIX y KISS, he optado por utilizar el formato N-Triples: Este consiste en un archivo de texto plano donde en cada línea hay una tupla. Esto, en conjunto con grep, awk y otros permite fácilmente realizar tareas que de otra forma serían mucho más difíciles.

Aunque un tanto artesanal, el uso de herramientas UNIX y archivos planos (N-Triples y listas/matrices de adyacencia) me ha dado buenos resultados para una serie de operaciones (aunque claro, estaría feliz de escuchar recomendaciones de otras plataformas ). Sin embargo quedan otros desafíos como el uso de memoria externa y paralelización de algoritmos que permitirían resolver (o aproximar) problemas mucho más complicados técnicamente tales como la ruta más corta entre todos los nodos y búsqueda de cliques, entre otros.