Iit-Tree: an Efficient Index to Support Interval-Based Query on Large Temporal Graphs

Graph is a powerful model to represent many-tomany relationships between entities and is widely used in mining social networks, managing communication networks, etc. The networks are usually not static and change over time. One of these types of networks is always represented by temporal graph, whose edges or vertices are available at a specific time. This incurs two challenges in managing temporal graphs: 1) a large amount of memory is required to store the graphs at different times, 2) querying or mining temporal graphs is inefficient as several graphs are involved within a query. Existing methods apply a $\Delta$ -based strategy to manage temporal graphs, which depend on the assumption that graphs within close time are similar. However, temporal graphs in the real world often fail to satisfy the above assumptions, which renders $\Delta$-based strategies ineffective in addressing the two challenges mentioned above. In this paper, we study two universal interval-based queries on the temporal graphs, i.e., durability query and existence query. To support the two kinds of queries, an index, IIT-Tree, is proposed without any assumption on the graphs. We also apply a compression strategy to further reduce the memory footprint of IIT-Tree, and integrate the optimized structure into an open-source system to enhance its applicability for graph-based applications. Extensive experiments on real data sets verify the superiority of IIT-Tree in managing and querying large temporal graphs.