Navegación

Búsqueda

Búsqueda avanzada

Trabajo Relevante – Efficient access methods for very large distributed graph databases

(Artículo ya publicado)

Resumen:

La búsqueda de subgrafos es un problema muy importante enel ámbito de las bases de datos de grafos. El problema presenta un granreto en lo que respecta a la eciencia de las soluciones, debido a la presenciadel isomorsmo de subgrafos, que es un problema NP-Completo.Los métodos de tipo Filter-Then-Verify (FTV) mejoran la eciencia medianteel uso de índices que evitan el tener que evaluar el isomorsmode subgrafos sobre todos los grafos almacenados. En aplicaciones reales,como la búsqueda de subestructuras moleculares, la búsqueda de subgrafosha de aplicarse sobre conjuntos de datos enormes (decenas demillones de elementos). Estudios anteriores han identicado a dos solutionsde tipo FTV, GrahpGrepSX (GGSX) y CT-Index, como las demejor eciencia al aplicarse en bases de datos de miles de elementos,sin embargo, su eciencia en conjuntos de datos realmente grandes noes la apropiada. En este trabajo se propone una aproximación genéricapara la implementación de soluciones de tipo FTV en entornos de procesamientodistribuido. Además, se adaptan tres métodos anteriormentepropuestos, que mejoran el rendimiento de GGXS y CT-Index, para serejecutados en clusters de computación. La evaluación muestra como lassoluciones propuestas proporcionan grandes mejoras de rendimiento en eltiempo de ltrado cuando son ejecutadas en arquitecturas centralizadas,y además permiten evaluar de forma eciente la búsqueda de subgrafosen bases de datos de gran volumen aprovechando las capacidades de lasarquitecturas distribuidas.

Palabras Clave:

Graph Databases - Graph indexing - Graph query processing - Large scale processing - Subgraph isomorphism - Subgraph search

Autor(es):

Handle:

11705/JISBD/2022/5050

Descargas:

Acceso a los detalles haciendo click aquí.