On More Efficiently and Versatilely Querying Historical k-Cores

Download PDF

Abstract

The recently proposed historical 𝑘-core query introduces a new paradigm of structure analysis for temporal graphs. However, the query processing based on the existing PHC-index, which preserves the distinct “core time” of each vertex, needs to traverse all vertices for each query, even though the results usually contain only a small subset of vertices. Inspired by the traditional 𝑘-shell that ensures the optimal 𝑘-core query processing, we propose a novel concept called “core time shell”, which reveals the hierarchical structure of vertices with respect to their core time. Based on the core time shell, we design a time-space balanced Merged Core Time Shell index (MCTS-index). It is theoretically guaranteed that, the MCTS-index provides the approximately optimal query performance, and has the approximately same space complexity as the PHC-index. Moreover, we leverage the MCTS-index to efficiently address the brand-new “when” historical 𝑘-core queries orthogonal to the current “what” historical 𝑘 -core queries. Our experimental results on ten real-world temporal graphs demonstrate both the superior efficiency of pro- cessing “what” queries and the effectiveness of processing versatile “when” queries for the MCTS-index.