TurboFlux

Abstract

A dynamic graph is defined by an initial graph and a graph update stream consisting of edge insertions and deletions. Identifying and monitoring critical patterns in the dynamic graph is important in various application domains such as fraud detection, cyber security, and emergency response. Given a dynamic data graph and a query graph, a continuous subgraph matching system reports positive matches for an edge insertion and reports negative matches for an edge deletion. Previous systems show significantly low throughput due to either repeated subgraph matching for each edge update or expensive overheads in maintaining enormous intermediate results. We present a fast continuous subgraph matching system called TurboFlux which provides high throughput over a fast graph update stream. TurboFlux employs a concise representation of intermediate results, and its execution model allows fast incremental maintenance. Our empirical evaluation shows that TurboFlux significantly outperforms existing competitors by up to six orders of magnitude.