An Index for Single Source All Destinations Distance Queries in Temporal Graphs

Typical tasks in analyzing temporal graphs are single-source-all-destination (SSAD) temporal distance queries, which are, e.g., common during the computation of centrality measures in temporal social networks. An SSAD query starting at a vertex $v$ asks for the temporal distances, e.g., durations, earliest arrival times, or the number of hops, between $v$ and all other reachable vertices. We introduce a new index to speed up SSAD temporal distance queries. The indexing is based on the construction of $k$ subgraphs and a mapping from the vertices to the subgraphs. Each subgraph contains the temporal edges sufficient to answer queries starting from any vertex mapped to the subgraph. We answer a query starting at a vertex $v$ with a single pass over the edges of the subgraph. The new index supports dynamic updates, i.e., efficient insertion and deletion of temporal edges. We call our index Substream index and show that deciding if there exists a Substream index of a given size is NP-complete. We provide a greedy approximation that constructs an index at most $k/\delta$ times larger than an optimal index where $\delta$, with $1\leq\delta\leq k$, depends on the temporal and spatial structure of the graph. Moreover, we improve the running time of the approximation in three ways. First, we use a secondary index called Time Skip index. It speeds up the construction and queries by skipping edges that do not need to be considered. Next, we apply min-hashing to avoid costly union operations. Finally, we use parallelization to take the parallel processing capabilities of modern processors into account. Our extensive evaluation using real-world temporal networks shows the efficiency and effectiveness of our indices.