Noticias
Diciembre, 2023.- Una de las múltiples líneas de trabajo desarrolladas en el Instituto Milenio Fundamentos de los Datos es la de grafos multimodales (uno de los desarrollos de esta área es Millenium DB). Los grafos multimodales son formas de estructurar los datos, representando relaciones entre diferentes tipos de nodos y conexiones, lo que permite modelar y representar información de diferentes tipos. Un ejemplo en el que se pueden usar es en el análisis de las redes de transporte de una zona: los nodos podrían ser los paraderos y las conexiones, las rutas entre los diferentes medios de transporte: bicicletas, automóviles, buses, etc. Analizar en este formato este tipo de información, permite tener un conocimiento mucho más completo y complejo que analizando esta misma información en formatos de bases de datos.
«Los grafos multimodales 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”, explica Gonzalo Navarro, académico del DCC U. Chile y uno de los investigadores del Instituto Milenio Fundamentos de los Datos tras “Worst-Case-Optimal Similarity Joins on Graph Databases”.
Este es el trabajo recientemente aceptado en la conferencia SIGMOD’24, en el cual trabajaron los académicos del DCC U. Chile Benjamín Bustos, Aidan Hogan y Gonzalo Navarro, en conjunto con los académicos DCC UC y Diego Arroyuelo y Juan Reutter; y Adrián Gómez-Brandón de la Universidade da Coruña)., todos investigadores del Instituto Milenio Fundamentos de los Datos
«El IMFD nos permite conversar y reunir los esfuerzos que realizamos entre centros y universidades diferentes», destaca Juan Reutter, director del IMFD y uno de los autores del trabajo. «Este logro es un claro ejemplo de lo que podemos lograr con el trabajo conjunto que realizamos en el Instituto Milenio Fundamentos de los Datos, ya que es aquí donde podemos potenciar las investigaciones que realizamos de forma independiente en las universidades, creando un espacio de colaboración que permite al país posicionarse a la vanguardia de la investigación a nivel latinoamericano en este y otros temas».
ACM SIGMOD es 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 de Chile.
Sumando más información
Sobre esta investigación, 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 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). El objetivo, señala Navarro, era además mantener la condición de worst-case-optimality de los algoritmos de búsqueda.
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.
—
Fuente: Comunicaciones DCC
