Graph data structures model relations between entities in various 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, many applications are dynamic in nature, and this reflects to graphs that continuously evolve over time. In these contexts, 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 middleware for temporal pattern recognition in large scale graphs. 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.

Temporal Pattern Recognition in Graph Data Structures

Hassan Nazeer Chaudhry;Alessandro Margara;Matteo Rossi
2021

Abstract

Graph data structures model relations between entities in various 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, many applications are dynamic in nature, and this reflects to graphs that continuously evolve over time. In these contexts, 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 middleware for temporal pattern recognition in large scale graphs. 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.
2021 IEEE International Conference on Big Data (Big Data)
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11311/1198509
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact