Horae: A Graph Stream Summarization Structure for Efficient Temporal Range Query

Horae is a graph stream summarization structure for efficient temporal range queries. Horae can deal with temporal queries with arbitrary and elastic range while guaranteeing one-sided and controllable errors. More to the point, Horae provides a worst query time of O(log L), where L is the length of query range. Hoare leverages multi-layer storage and Binary Range Decomposition (BRD) algorithm to decompose the temporal range query to logarithmic time interval queries and executes these queries in corresponding layers.

Introduction

The emerging graph stream represents an evolving graph formed as a timing sequence of elements (updated edges) through a continuous stream. Each element in a graph stream is formally denoted as (s_i, d_i,w_i, t_i) (i ≥ 0), meaning the directed edge of a graph G = (V, E), i.e., s_i → d_i (s_i ∈ V, d_i ∈ V, s_i → d_i ∈ E), is produced at time t_i with a weight value w_i. An edge can appear multiple times at different time instants with different weights. Such a general data form is widely used in big data applications, such as user behavior analysis in social networks, close contact tracking in epidemic prevention, and vehicle surveillance in smart cities.

Real-world big data applications can create tremendously large-scale graph stream data. The enormous data scale makes the management of graph streams extremely challenging, especially in the aspects of (1) storing the continuously produced and large-scale datasets, and (2) supporting queries relevant to both graph topology and temporal information. To address these issues, recent research has mainly focused on graph stream summarization techniques which aim at achieving practicable storage and supporting various queries relevant to graph topology at the cost of slight accuracy sacrifice.

However, existing summarization structures are unable to store the temporal information in a graph stream and thus fail to support temporal queries. In this work, we propose Horae, a novel graph stream summarization structure to efficiently support temporal range queries. By exploring a time prefix embedded multi-layer summarization structure, Horae can effectively handle a temporal range query of an arbitrary range length L with a worst query processing time of O(log L). The basic idea of Horae's time prefix embedded multi-layer summarization structure is as follows.

An arbitrary temporal range of length L can be decomposed to at most 2log L sub-ranges, where all the time points in each sub-range have the same binary code prefix. For example, [t₈, t₁₃] = [t₈, t₁₁] + [t₁₂, t₁₃], where all the time points between t₈ (i.e., 1000) and t₁₁ (i.e., 1011) have the same common prefix '10', while all the time points between t₁₂ (i.e., 1100) and t₁₃ (i.e., 1101) have the same prefix '110'. Here, we define the prefix size as the number of binary digits in the common prefix (e.g., the prefix size of '10' is two while that of '110' is three).

A Horae structure contains a number of l = ⌈ log₂(t_u + 1) ⌉ + 1 layers, where t_u is the current time point of a graph stream. To cope with the infinity in the time dimension, the number of layers in Horae dynamically increases as t_u grows. Horae arranges the layers according to different prefix sizes. Each layer leverages a matrix to store the complete graph stream data aggregated by the sub-ranges with the same prefix size. Consider the example with t_u = t₇, Horae has four layers. The first layer contains eight sub-ranges {[t₀] ([0000]), [t₁] ([0001]), ..., [t₇] ([0111])} with prefix size of four; the second layer contains four sub-ranges {[t₀, t₁] ([0000, 0001]), [t₂, t₃] ([0010, 0011]), ..., [t₆, t₇] ([0110, 0111])} with prefix size of three, and so on. Formally, the p^th layer aggregates the graph stream data by the sub-ranges {[{q ⋅ 2^{p - 1}}, {(q + 1) ⋅ 2^{p - 1}} - 1] (q ≥ 0)} with prefix size l - p + 1. The sub-ranges of each layer have the same prefix size, i.e., the same range length. In a nutshell, each layer of the structure represents a summarization of a graph stream with carefully selected granularity (corresponds to a prefix size). During the construction of each layer, Horae combines each edge with the time prefix of the corresponding size for inserting the edge information to the corresponding matrix. Similarly, Horae combines an edge/node and the sub-range prefix to perform a sub-range query.

To efficiently evaluate temporal range queries on top of the Horae structure, we further design a novel Binary Range Decomposition (BRD) algorithm. The BRD algorithm decomposes a temporal range query with an arbitrary length L into at most O(log L) sub-range queries against different layers of the structure. Therefore, Horae reduces the query processing time to a logarithmic scale. Experimental results show that Horae reduces the latency of temporal range queries by two to three orders of magnitude compared to existing designs.

Horae Structure

<img src="images/Horae-structure.png" width=1000 alt="Horae-structure"/><br/>

The Horae structure contains l = ⌈ log₂(T_u + 1) ⌉ + 1 layers. It starts with a single layer initially and creates one new layer whenever the current time slice of the graph stream increases to a larger power of two (T_u = 2ⁱ, i ≥ 0). Horae arranges the layers based on different prefix sizes. Each layer aggregates the complete graph stream data by a corresponding prefix size. In the snapshot, the 1^st layer contains four sub-ranges {[T₀] (000), [T₁] (001), ..., [T₃] (011)}, all with the prefix size of three; the 2^nd layer contains two sub-ranges {[T₀, T₁] (<u>00</u>0, <u>00</u>1), [T₂, T₃] (<u>01</u>0, <u>01</u>1)}, both with the prefix size of two; the 3^rd layer contains one sub-range {[T₀, T₃] (<u>0</u>00, <u>0</u>11)} with the prefix size of one. Formally, the p^th layer aggregates the graph stream data by the sub-ranges {[0, 2^{p - 1} - 1], [2^{p - 1}, 2 ⋅ 2^{p - 1} - 1], ...} with the same prefix size of l - p + 1. All the sub-ranges of the p^th layer have the same range length 2^{p - 1}. We define the same range length of each sub-range in the p^th layer as the granularity of the p^th layer. In a word, the p^th layer of Horae represents a graph stream summarization of granularity 2^{p - 1}.

Binary Range Decomposition

<img src="images/Horae-BRD-3cases.png" width=1000 alt="Horae-BRD-3cases"/><br/> We design the BRD algorithm to quickly decompose an arbitrary time range query to multiple window queries of different layers. For any time range of length L, we can find an m which satisfies 2^m ≤ L < 2^{m + 1} (i.e., m = ⌊ log₂ L ⌋). The granularity of the (m + 1)^th layer is 2^m. BRD is based on the observation: if the time range aligns with one side of a window in the (m + 1)^th layer, decomposing the range equals decomposing its length, i.e., converting L to binary form.

For convenience, we call a sub-range of each layer a window. We use the notation W_p^q to denote the window with prefix q in the p^th layer, and more generally W_p^q = [q ⋅ 2^{p - 1}, (q + 1) ⋅ 2^{p - 1} - 1]. For example, we have W₂² = [T₄, T₅]. For a window [T_i, T_j] of length N, [T_i, T_j] = W_(log₂N+1)^⌊T_i/N⌋ = W_(log₂N+1)^⌊T_j/N⌋. The windows of the p^th and (p + 1)^th layers have the following relationship: the two adjacent windows can be merged into a larger window of the upper layer. Formally, W_p²ⁱ + W_p^{2i + 1} = W_{p + 1}ⁱ (i ≥ 0), where W_p²ⁱ and W_p^{2i + 1} are called sibling windows.

Given an arbitrary query range [T_b, T_e] with the length L = T_e - T_b + 1, we formalize the decomposition result as follows: DE([T_b, T_e]) = W_p₁^q₁ + W_p₂^q₂ + ... + W_{p_f}^q_f, where W_{p_i}^q_i and W_{p_j}^q_j cannot be sibling windows for any two i, j ∈ [1, f] and i ≠ j. Here, we identify an important property of the window: for a time range [T_i, T_j] of length N (N = 2^k (k ≥ 0)), it is a window if and only if (T_j + 1) % N = 0.

For an arbitrary time range, it may align perfectly with a window, align with one side of a window, or not align with any window in the (m + 1)^th layer. Accordingly, we summarize the