Symmetric continuous subgraph matching with bidirectional dynamic programming - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Symmetric continuous subgraph matching with bidirectional dynamic programming

Résumé

In many real datasets such as social media streams and cyber data sources, graphs change over time through a graph update stream of edge insertions and deletions. Detecting critical patterns in such dynamic graphs plays an important role in various application domains such as fraud detection, cyber security, and recommendation systems for social networks. Given a dynamic data graph and a query graph, the continuous subgraph matching problem is to find all positive matches for each edge insertion and all negative matches for each edge deletion. The state-of-the-art algorithm TurboFlux uses a spanning tree of a query graph for filtering. However, using the spanning tree may have a low pruning power because it does not take into account all edges of the query graph. In this paper, we present a symmetric and much faster algorithm SymBi which maintains an auxiliary data structure based on a directed acyclic graph instead of a spanning tree, which maintains the intermediate results of bidirectional dynamic programming between the query graph and the dynamic graph. Extensive experiments with real and synthetic datasets show that SymBi outperforms the state-of-the-art algorithm by up to three orders of magnitude in terms of the elapsed time.
Fichier principal
Vignette du fichier
2104.00886.pdf (1.12 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03498315 , version 1 (21-12-2021)

Identifiants

Citer

Seunghwan Min, Sung Gwan Park, Kunsoo Park, Dora Giammarresi, Giuseppe Italiano, et al.. Symmetric continuous subgraph matching with bidirectional dynamic programming. VLDB 2021 - 47th International Conference on Very Large Data Bases, Aug 2021, Copenhagen, Denmark. pp.1298-1310, ⟨10.14778/3457390.3457395⟩. ⟨hal-03498315⟩

Collections

INRIA INRIA2
14 Consultations
46 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More