TC-Match: Emparejamiento Continua de Subgrafos Rápido y Constricción Temporal

Monitorear continuamente patrones estructurales en grafos en streaming es una tarea crítica en muchas aplicaciones en tiempo real basadas en grafos. En este artículo, estudiamos el problema del emparejamiento continuo de subgrafos con constricción temporal (abreviado como TCSM) sobre grafos en streaming. Dado un grafo de consulta Q con una restricción de orden temporal y un flujo de grafo de datos G, TCSM tiene como objetivo reportar todas las coincidencias incrementales de Q en G con cada actualización de G, donde una coincidencia debe cumplir tanto la restricción de estructura (es decir, isomorfismo) como la restricción de orden temporal de Q. Aunque TCSM tiene un amplio rango de aplicaciones, como la detección de ciberataques y la detección de fraude con tarjetas de crédito, notamos que este problema no ha sido bien abordado. El estado del arte presenta limitaciones en cuanto al alto costo del espacio de índices y el costo de mantenimiento de resultados intermedios. En este artículo, proponemos TC-Match, un enfoque efectivo para TCSM. Primero, diseñamos un índice CSS que es rentable en términos de espacio y tiempo, que es esencialmente una estructura de grafo k-partita donde un nodo corresponde a una arista en G. Al crear cuidadosamente enlaces entre nodos, podemos encapsular en CSS la información de emparejamiento parcial y el orden temporal entre las aristas en G. Mostramos teóricamente que CSS tiene complejidades de espacio y tiempo de construcción polinómicas. En segundo lugar, basado en la propiedad de CSS, desarrollamos un algoritmo de emparejamiento incremental eficiente con una optimización efectiva de fusión de nodos. Experimentos exhaustivos muestran que TC-Match puede lograr hasta 3 órdenes de magnitud de mejora en rendimiento de consulta sobre los métodos base, y al mismo tiempo, el consumo de memoria se reduce entre un 48.7% y un 86.7%.