Consulta dinámica de subgráficos interesantes Top-K en gráficos etiquetados a gran escala
Autores: Shan, Xiaohuan; Jia, Chunjie; Ding, Linlin; Ding, Xingyan; Song, Baoyan
Idioma: Inglés
Editor: MDPI
Año: 2019
Acceso abierto
Artículo científico
2019
Consulta dinámica de subgráficos interesantes Top-K en gráficos etiquetados a gran escala
Categoría
Gestión y administración
Subcategoría
Gestión de la tecnología y la inovación
Palabras clave
Grafo etiquetado
Consulta de subgrafo
Top-K dinámico
índice GTSF
índice NTF
índice EF
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 1
Citaciones: Sin citaciones
Un grafo etiquetado es una estructura especial con capacidad de identificación de nodos, que se utiliza a menudo en redes de información, redes biológicas y otros campos. La consulta de subgrafos se utiliza ampliamente como un medio importante de análisis de datos de grafos. A medida que el tamaño del grafo etiquetado aumenta y cambia dinámicamente, los usuarios tienden a centrarse en los resultados de alta coincidencia que les interesan, y quieren aprovechar la relación y el número de resultados para obtener rápidamente los resultados de la consulta. Por esta razón, consideramos las necesidades individuales de los usuarios y proponemos una consulta dinámica de subgrafos interesantes Top-K. Este método establece un nuevo índice de características de topología de grafo (índice GTSF) que incluye un índice de características de topología de nodos (índice NTF) y un índice de características de aristas (índice EF), que puede podar y filtrar de manera efectiva los nodos y aristas inválidos que no cumplen con la condición restringida. Se propone una estrategia de filtrado del conjunto de candidatos multifactorial basada en el índice GTSF, que puede ser podada aún más para obtener menos conjuntos de candidatos. Luego, proponemos un método de consulta dinámica de subgrafos interesantes Top-K basado en la idea de la ventana deslizante para realizar la modificación dinámica de los resultados de coincidencia del subgrafo en la evolución dinámica del grafo etiquetado, para garantizar resultados de consulta en tiempo real y precisos. Además, considerando factores como la frecuencia de entrada/salida (I/O) y los costos de comunicación en red, se proponen un mecanismo de optimización de los cambios en el grafo y una estrategia de mantenimiento incremental para el índice para reducir el enorme costo de operaciones redundantes y actualizaciones globales. Los resultados experimentales muestran que el método propuesto puede manejar de manera efectiva una consulta dinámica de subgrafos interesantes Top-K en un grafo etiquetado a gran escala, al mismo tiempo que el mecanismo de optimización de cambios en el grafo y la estrategia de mantenimiento incremental del índice pueden reducir efectivamente los costos de mantenimiento.
Descripción
Un grafo etiquetado es una estructura especial con capacidad de identificación de nodos, que se utiliza a menudo en redes de información, redes biológicas y otros campos. La consulta de subgrafos se utiliza ampliamente como un medio importante de análisis de datos de grafos. A medida que el tamaño del grafo etiquetado aumenta y cambia dinámicamente, los usuarios tienden a centrarse en los resultados de alta coincidencia que les interesan, y quieren aprovechar la relación y el número de resultados para obtener rápidamente los resultados de la consulta. Por esta razón, consideramos las necesidades individuales de los usuarios y proponemos una consulta dinámica de subgrafos interesantes Top-K. Este método establece un nuevo índice de características de topología de grafo (índice GTSF) que incluye un índice de características de topología de nodos (índice NTF) y un índice de características de aristas (índice EF), que puede podar y filtrar de manera efectiva los nodos y aristas inválidos que no cumplen con la condición restringida. Se propone una estrategia de filtrado del conjunto de candidatos multifactorial basada en el índice GTSF, que puede ser podada aún más para obtener menos conjuntos de candidatos. Luego, proponemos un método de consulta dinámica de subgrafos interesantes Top-K basado en la idea de la ventana deslizante para realizar la modificación dinámica de los resultados de coincidencia del subgrafo en la evolución dinámica del grafo etiquetado, para garantizar resultados de consulta en tiempo real y precisos. Además, considerando factores como la frecuencia de entrada/salida (I/O) y los costos de comunicación en red, se proponen un mecanismo de optimización de los cambios en el grafo y una estrategia de mantenimiento incremental para el índice para reducir el enorme costo de operaciones redundantes y actualizaciones globales. Los resultados experimentales muestran que el método propuesto puede manejar de manera efectiva una consulta dinámica de subgrafos interesantes Top-K en un grafo etiquetado a gran escala, al mismo tiempo que el mecanismo de optimización de cambios en el grafo y la estrategia de mantenimiento incremental del índice pueden reducir efectivamente los costos de mantenimiento.