  Querying cohesive subgraphs on temporal graphs with various time constraints
has attracted intensive research interests recently. In this paper, we study a
novel Temporal k-Core Query (TCQ) problem: given a time interval, find all
distinct k-cores that exist within any subintervals from a temporal graph,
which generalizes the previous historical k-core query. This problem is
challenging because the number of subintervals increases quadratically to the
span of time interval. For that, we propose a novel Temporal Core Decomposition
(TCD) algorithm that decrementally induces temporal k-cores from the previously
induced ones and thus reduces "intra-core" redundant computation significantly.
Then, we introduce an intuitive concept named Tightest Time Interval (TTI) for
temporal k-core, and design an optimization technique with theoretical
guarantee that leverages TTI as a key to predict which subintervals will induce
duplicated k-cores and prunes the subintervals completely in advance, thereby
eliminating "inter-core" redundant computation. The complexity of optimized TCD
(OTCD) algorithm no longer depends on the span of query time interval but only
the scale of final results, which means OTCD algorithm is scalable. Moreover,
we propose a compact in-memory data structure named Temporal Edge List (TEL) to
implement OTCD algorithm efficiently in physical level with bounded memory
requirement. TEL organizes temporal edges in a "timeline" and can be updated
instantly when new edges arrive, and thus our approach can also deal with
dynamic temporal graphs. We compare OTCD algorithm with the incremental
historical k-core query on several real-world temporal graphs, and observe that
OTCD algorithm outperforms it by three orders of magnitude, even though OTCD
algorithm needs none precomputed index.
