“Worst-Case-Optimal Similarity Joins on Graph Databases” se titula la investigación, recientemente aceptada en la conferencia SIGMOD'24, desarrollada por los académicos del DCC Benjamín Bustos, Aidan Hogan y Gonzalo Navarro, en conjunto con los académicos Diego Arroyuelo (U. Católica), Adrián Gómez-Brandón (Universidade da Coruña) y Juan Reutter (U. Católica). Además, todos los autores de este trabajo, son investigadores del Instituto Milenio Fundamentos de los Datos (IMFD). 

Sobre esta investigación, el profesor Gonzalo Navarro explica: “Existe mucho trabajo reciente de las llamadas bases de datos de grafos, que representan la información en forma de nodos (los objetos) y aristas que conectan nodos (y representan relaciones entre los objetos), porque son más flexibles que las bases de datos relacionales. Estos grafos se consultan principalmente mediante dar un pequeño grafo patrón, que tiene nodos y aristas pero donde las identidades de los nodos y de las aristas pueden ser variables. Cada forma de darle valor a las variables para que ese patrón aparezca en el grafo, es una respuesta a la consulta. Como ejemplo muy simplificado, en un grafo con información sobre farmacias, una consulta como (F, vende, X), (X, componente, paracetamol), (X, precio, P), (F, tiene-convenio, Fonasa), me entrega las farmacias F con convenio con Fonasa que venden algún medicamento X con paracetamol, y el precio P al que lo venden. Responder a esas consultas eficientemente no es fácil, y no es raro que algunas tomen segundos y hasta minutos. Un estándar de calidad para estos algoritmos es ser worst-case optimal. Este tipo de algoritmos es relativamente reciente y aún hay mucha investigación sobre ellos”. 

En este contexto, el académico expresa que una línea de trabajo desarrollada en el IMFD es la llamada grafos multimodales, “que contienen más semántica que la mera conectividad entre los nodos. Este tipo de información es muy frecuente en la vida real y para ser consultada efectivamente requiere enriquecer el lenguaje de los grafos patrones con expresiones específicas de los tipos de datos. Por ejemplo, algunos nodos pueden ser lugares geográficos y tener asociada información de su ubicación, y yo quisiera poder buscar la consulta anterior, pero restringida a que la farmacia esté en un cierto radio de distancia. O que la hora actual esté entre su horario de apertura y cierre. O que el precio sea menor a cierto límite”.

El profesor Gonzalo Navarro señala que en este artículo científico se aborda el problema de poder agregar información métrica a los objetos y condiciones de cercanía a los grafos patrones. Explica que las métricas son generalizaciones de las distancias euclidianas (como las del plano o el espacio), que abarcan no sólo el ejemplo de distancia geográfica sino otras como similitud entre imágenes, audio, video, textos, etc. (que se modelan como distancias en espacios de dimensiones muy altas). “Queríamos además mantener la condición de worst-case-optimality de los algoritmos de búsqueda”, afirma. 

De este modo, los investigadores muestran que es posible incluir este tipo de información y soportar un tipo particular de consultas, “que es la de los k vecinos más cercanos. Se forma, entre los objetos que tienen la métrica, un grafo donde cada nodo sabe cuáles son los k nodos más cercanos/parecidos a él. La consulta entonces puede pedir que un objeto esté entre los k más cercanos/parecidos a otro. Esto nos permite preguntar, por ejemplo, por iglesias en mi misma ciudad cuya fachada se parezca (como imagen) a una que me interesa. Mostramos que el grafo de los k vecinos se puede unir al grafo de la base de datos de modo de integrarlo elegantemente en el mismo algoritmo worst-case-optimal, reutilizando de cierta forma todo el desarrollo ya conocido sobre este algoritmo. Mostramos que, en varios casos, podemos retener la worst-case-optimality, aunque no en todos. E implementamos el nuevo algoritmo y mostramos que es bastante mejor que una solución básica. Esto abre la puerta a soportar otros tipos de consultas (por distancia, como en el ejemplo de las farmacias), y otros tipos de datos (topológicos, de regiones geográficas, temporales, etc.)”, comenta el académico.

“Worst-Case-Optimal Similarity Joins on Graph Databases”, será presentando en ACM SIGMOD, una de las conferencias principales de bases de datos –junto con ACM PODS–, centrada en los principios, técnicas y aplicaciones de sistemas y tecnologías de manejo de bases de datos, y que en 2024 se realizará en Santiago.

--
Comunicaciones DCC