Resumen:
Efficient access methods for very large distributed graph databases

Fecha

2022-09-05

Editor

Sistedes

Publicado en

Actas de las XXVI Jornadas de Ingeniería del Software y Bases de Datos (JISBD 2022)

Licencia

CC BY-NC-ND 4.0

Resumen

La búsqueda de subgrafos es un problema muy importante en el ámbito de las bases de datos de grafos. El problema presenta un gran reto en lo que respecta a la eciencia de las soluciones, debido a la presencia del isomorsmo de subgrafos, que es un problema NP-Completo. Los métodos de tipo Filter-Then-Verify (FTV) mejoran la eciencia mediante el uso de índices que evitan el tener que evaluar el isomorsmo de subgrafos sobre todos los grafos almacenados. En aplicaciones reales, como la búsqueda de subestructuras moleculares, la búsqueda de subgrafos ha de aplicarse sobre conjuntos de datos enormes (decenas de millones de elementos). Estudios anteriores han identicado a dos solutions de tipo FTV, GrahpGrepSX (GGSX) y CT-Index, como las de mejor eciencia al aplicarse en bases de datos de miles de elementos, sin embargo, su eciencia en conjuntos de datos realmente grandes no es la apropiada. En este trabajo se propone una aproximación genérica para la implementación de soluciones de tipo FTV en entornos de procesamiento distribuido. Además, se adaptan tres métodos anteriormente propuestos, que mejoran el rendimiento de GGXS y CT-Index, para ser ejecutados en clusters de computación. La evaluación muestra como las soluciones propuestas proporcionan grandes mejoras de rendimiento en el tiempo de ltrado cuando son ejecutadas en arquitecturas centralizadas, y además permiten evaluar de forma eciente la búsqueda de subgrafos en bases de datos de gran volumen aprovechando las capacidades de las arquitecturas distribuidas.

Descripción

Acerca de Luaces Cachaza, David

Palabras clave

Graph Databases, Graph Indexing, Graph Query Processing, Large Scale Processing, Subgraph Isomorphism, Subgraph Search
Página completa del ítem
Notificar un error en este resumen
Mostrar cita
Mostrar cita en BibTeX
Descargar cita en BibTeX