Time Windowed Data Structures for Graphs
Farah Chanchary and Anil Maheshwari
Vol. 23, no. 2, pp. 191-226, 2019. Regular paper.
Abstract We present data structures that can answer time windowed queries for a set of timestamped events in a relational event graph. We study the relational event graph as input to solve (a) time windowed decision problems for monotone graph properties, such as disconnectedness and bipartiteness, and (b) time windowed reporting problems such as reporting the minimum spanning tree, the minimum time interval, and the graph edit distance for obtaining spanning forests. We also present results of window queries for counting subgraphs of a given pattern, such as paths of length 2 (in general graphs) and paths of length 3 (in bipartite graphs), quadrangles and complete subgraphs of a fixed order or of all orders $\ell \geq 3$ (i.e., cliques of size $\ell$). These query results can be used to compute graph parameters that are important for social network analysis, e.g., clustering coefficients, embeddedness and neighborhood overlapping.
Submitted: December 2017.
Reviewed: May 2018.
Revised: July 2018.
Reviewed: October 2018.
Revised: October 2018.
Accepted: February 2019.
Final: February 2019.
Published: February 2019.
Communicated by Anna Lubiw
article (PDF)