Temporal Graph Cube

Data warehouse and OLAP (Online Analytical Processing) are effective tools for decision support on traditional relational data and static multidimensional network data. However, many real-world multidimensional networks are often modeled as temporal multidimensional networks, where the edges in the network are associated with temporal information. Such temporal multidimensional networks typically cannot be handled by traditional data warehouse and OLAP techniques. To fill this gap, we propose a novel data warehouse model, named $\mathsf {Temporal{ }\; Graph{ }\; Cube}$, to support OLAP queries on temporal multidimensional networks. Through supporting OLAP queries in any time range, users can obtain summarized information of the network in the time range of interest, which cannot be derived by using traditional static graph OLAP techniques. We propose a segment-tree based indexing technique to speed up the OLAP queries, and also develop an index-updating technique to maintain the index when the temporal multidimensional network evolves over time. In addition, we also propose a novel concept called $\mathsf {similarity{ }\; of{ }\; snapshots}$ which shows a strong correlation with the efficiency of indexing technique and can provide a good reference on the necessity of building the index. The results of extensive experiments on two large real-world datasets demonstrate the effectiveness and efficiency of the proposed method.

I. Introduction

Data warehouses and OLAP (Online Analytical Processing) techniques are helpful tools for knowledge workers (executive, manager, analyst) to analyze and make decisions, because Data warehouses and OLAP together can efficiently provide summarized information in different resolutions by specifying different views (different combinations of data dimensions) of large-scale real-world data through OLAP operations such as roll-up, drill-down and slice-and-dice [1]. Data warehouse built on traditional relational database (RDB) data is called data cube [2]. In 2011, Zhao et al. [3] proposed $\mathsf {Graph}$ $\mathsf {Cube}$ which extends data warehouses and OLAP techniques to analyze static multidimensional networks. For each query, static graph cube returns a static network with summarized information in its structure and statistical values on vertices and edges.