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

A typical task in temporal graphs analysis is answering single-source-all-destination (SSAD) temporal distance queries. An SSAD query starting at a vertex $v$ asks for the temporal distances, e.g., durations or earliest arrival times between $v$ and all other vertices. We introduce an index to speed up SSAD temporal distance queries called Substream index. 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. Our index supports dynamic updates, i.e., efficient insertion and deletion of temporal edges. Unfortunately, deciding if a Substream index of a given size exists is NP-complete. However, we provide an efficient 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 an auxiliary index called Time Skip index to speed 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. An extensive evaluation using real-world temporal networks shows the efficiency and effectiveness of our indices, and query times are significantly improved for all data sets.