Design and implementation of FlowGraph, a distributed framework for temporal pattern recognition in graph data structures

Graph data structures model relations between entities in many diverse application domains. Graph processing systems enable scalable distributed computations over large graphs, but are limited to static scenarios in which the structure of the graph does not change. However, virtually all applications are dynamic in nature, and this reflects to graphs that continuously evolve over time. Understanding the evolution of graphs is key to enable timely reactions when necessary. We address this problem by proposing a new model to express temporal patterns over graph data structures. The model seamlessly integrates computations over graphs to extract relevant values, and temporal operators that define patterns of interest in the evolution of the graph. We present the syntax and semantics of our model and discuss its concrete implementation in Flowgraph, a distributed framework for temporal pattern recognition in large scale graphs. We thoroughly evaluate the performance and scalability of Flowgraph with various workloads. Flowgraph presents a level of performance that is comparable to state-of-the-art graph processing tools when processing static graphs. In the presence of temporal patterns, it can further optimize processing by avoiding complex graph computations until strictly necessary for pattern evaluation.

Le strutture dati a grafo modellano le relazioni tra le entità in diversi domini applicativi. I sistemi di processamento dei grafi attuali permettono di effettuare computazioni distribuite in grado di scalare su grafi di dimensioni elevate, tuttavia sono limitati a scenari statici nel quale la struttura del grafo non cambia nel tempo. Tuttavia, potenzialmente tutte le applicazioni hanno una natura dinamica e questo si riflette in strutture a grafo che evolvono continuamente nel tempo. Comprendere l'evoluzione dei grafi è un fattore chiave che permettere di reagire, ove necessario, in tempo reale. Abbiamo affrontato il problema proponendo un nuovo modello per esprimere pattern temporali sui grafi. Il modello integra computazioni continue sul grafo, per estrarre quelli che sono i valori ritenuti rilevanti per la valutazione, ed operatori temporali che definiscono i pattern di interesse nell'evoluzione del grafo. Presentiamo la sintassi e la semantica del nostro modello e ne offriamo una sua concreta implementazione in Flowgraph, un framework distribuito per il riconoscimento di pattern temporali su grafi di grandi dimensioni. Valutiamo poi nel dettaglio le performance e la scalabilità di Flowgraph con diversi workload. Flowgraph presenta un livello di performance paragonabile all'attuale stato dell'arte degli strumenti di processamento di grafi statici. In presenza di pattern temporali, FlowGraph riesce ulteriormente ad ottimizzare l'esecuzione evitando computazioni complesse sul grafo se non strettamente necessarie per la valutazione del pattern.