An Axiomatic Approach to Time-Dependent Shortest Path Oracles

Abstract

Computing shortest paths in networks that exhibit a time-dependent metric is a core routine for many applications, with route planning in road networks being a prime example. In this work, we present an axiomatic approach which shows that for directed networks that satisfy certain properties we can provide time-dependent distance oracles that provably exhibit subquadratic preprocessing time and space (independent of the metric’s amount of disconcavity), query time sublinear on the network size or the actual Dijkstra rank of the query at hand (measuring the distance ordering of the destination from the origin), and small stretch factor (approximation error).

Appendices

Summary of Notation

The following table provides a summary of the most commonly used notation throughout the paper.

Notation	Description
Arr[a](t)	The arc-arrival-time of arc $a=uv\in A$ as a function of the departure time t from u.
Arr[o, d](t)	Earliest-arrival-time from o to d as a function of the departure time t from o.
${ASP[o,d;\varepsilon ](t_o)}$	Set of $(1+\varepsilon )$-approximations of minimum-travel-time od-paths in G, for given departure-time $t_o\ge 0$.
$B[v;\mathrm {radius}=R](t_v)$	A ${\mathtt {TDD}}$ ball growing from $(v,t_v)\in V\times [0,T)$, in the time-dependent metric, of radius R.
$B[v;\mathrm {size}=F](t_v)$	A ${\mathtt {TDD}}$ ball growing from $(v,t_v)\in V\times [0,T)$, in the time-dependent metric, of size $F\in \mathbb {N}$.
${\overline{B}}[v;\mathrm {size}=F]$ / ${\underline{B}}[v;\mathrm {size}=F]$	A ${\mathtt {TDD}}$ ball growing from $v\in V$, in the full-congestion / free flow metric, of (integer) size $F\in \mathbb {N}$.
${\overline{B}}[v;\mathrm {radius}=R]$ / ${\underline{B}}[v;\mathrm {radius}=R]$	A ${\mathtt {TDD}}$ ball growing from $v\in V$, in the full-congestion / free flow metric, of (scalar) radius $R>0$.
${\mathtt {BIS}}$	The bisection approximation method for minimum-travel-time functions [17].
${\mathtt {BIS}}^+$	The variant of ${\mathtt {BIS}}$ introduced in this paper.
$C[\ell ]$	Area of coverage of landmark $\ell$ (set of vertices for which $\ell$ possesses travel-time summaries).
$\varGamma [o,d](t)$	Dijkstra-Rank from o to d as a function of the departure time t from o (number of settled vertices when executing ${\mathtt {TDD}}(o,\star ,t)$ until d is settled).
d[uv](t)	The limited-window arc-travel-time function for arc $uv\in A$, with departure-time $t\in [0,T)$ for some constant time-period $T>0$ (e.g., a single day).
D[uv](t)	Periodic arc-travel-time function for arc $uv\in A$, with domain $t\in [0,\infty )$.
${\overline{D}}[a]$ & ${\underline{D}}[a]$	Scalar travel-times of a in full-congestion and free-flow metrics, respectively.
D[o, d](t)	Minimum-travel-time from o to d as a function of the departure time t from o.
$D_{\max }[o,d]$ / $D_{\min }[o,d]$	The maximum / minimum value of D[o, d].
${\overline{\varDelta }}[o,d](t)$ / ${\underline{\varDelta }}[o,d](t)$	An upper-approximating / lower-approximating function to D[o, d](t).
diam(G, D)	The diameter of G under an arc-cost metric D.
F	$F = \max _{\ell \in L}\left\{ |{\underline{B}}[\ell ;\mathrm {radius}={\underline{R}}]| \right\}$ maximum number of nearby vertices around any landmark, for a fixed ${\underline{R}}$.
$\zeta$	Ratio of minimum-travel-times in opposite directions between two vertices for any specific departure-time.
${\mathtt {FCA}}$	The Forward Constant Approximation query algorithm [17].
${\mathtt {FCA}}^+$	The variant of ${\mathtt {FCA}}$ introduced in this paper.
${\mathtt {FLAT}}$	The TD-oracle whose preprocessing is based on a proper combination of ${\mathtt {BIS}}^+$ and ${\mathtt {TRAP}}$ and uses ${\mathtt {RQA}}^+$ as its query algorithm.
$G=(V,A)$	The graph representing the underlying structure of the time-dependent network instance; $n = |V|$ and $m=|A|$.
${\mathtt {HORN}}$	The oracle that uses a hierarchy of landmarks with their own subset of destination vertices, and the ${\mathtt {HQA}}$ query algorithm.
${\mathtt {HQA}}$	The Hierarchical Query Algorithm, based on a hierarchy of landmarks.
$\mathbf {iuar}(\rho )$	Independently and uniformly at random with probability $\rho$.
[k]	The set of integers $\{1,2,\ldots , k\}$, for any $k\in \mathbb {N} -\{0\}$.
$K_a$	Number of breakpoints in the arc-travel-time function D[a].
K	Total number of breakpoints in the arc-travel-time functions.

Notation	Description
$K_{\max }$	The maximum number of breakpoints, among the arc-travel-time functions.
$K^*$	Total number of concavity-spoiling breakpoints (i.e., points at which the slope increases) in the arc-travel-time functions.
$\varLambda _{\max }$	Maximum slope among minimum-travel-time functions.
$\varLambda _{\min }$	Absolute value of minimum slope among minimum-travel-time functions.
$\ell _o$	$\arg \min _{\ell \in L}\{ D[o,\ell ](t_o)\}$ (closest settled landmark when growing a ${\mathtt {TDD}}$ ball from $(o,t_o)$).
MAE	Maximum Absolute Error.
$N_i$	Targeted Dijkstra-rank for the i-th level in the hierarchy of landmarks in ${\mathtt {HORN}}$.
${\mathcal {P}}_{o,d}$	Set of od-paths in G.
$p \bullet q$	The concatenation of an ux-path p with an xv-path q at vertex x.
pwl	piece-wise linear
$SP[o,d](t_o)$	Set of minimum-travel-time od-paths in G, for given departure-time $t_o\ge 0$.
${\underline{R}}$	Free-flow distance ${\underline{R}} = T^{\theta }$, for constant $\theta \in (0,1)$.
$R_o$	$D[o,\ell _o](t_o)$ (minimum travel time to closest landmark $\ell _o$ from o).
$R_d$	$D[o,d](t_o)$ (minimum travel time to d when departing at time $t_o$ from o).
r	The recursion budget (or depth) of ${\mathtt {RQA}}$ and ${\mathtt {HQA}}$.
radius(B)	$\max \{ D[v,x](t_v) : x\in B\}$ (longest travel-time in a ${\mathtt {TDD}}$ ball B from its center $(v,t_v)$ to any destination x).
${\underline{radius}}(B)$ / ${\overline{radius}}(B)$	The radius of B under the (static) free-flow / full-congestion metric.
$RING[o;i](t_o)$	The difference of two cocentric ${\mathtt {TDD}}$ balls around vertex o, the one containing the $N_i\ln (n)$ closest destinations from o, and the other containing the $\frac{N_i}{\ln (n)}$ closest destinations from o.
${\mathtt {RQA}}$	The Recursive Query Algorithm, based on landmarks possessing information towards all possible destinations [17].
${\mathtt {RQA}}^+$	The variant of ${\mathtt {RQA}}$ introduced in this paper.
${\mathtt {RQA}}^+_i$	The variant of ${\mathtt {RQA^+}}$ which only uses landmarks from $M_i = \cup _{j=i}^{k+1} L_j$ in the hierarchy of ${\mathtt {HORN}}$.
$t_u ~~ (t_v)$	Departure-time from the tail u (arrival-time at the head v) of an arc $uv\in A$.
T	Time period of arc functions; $T=n^\alpha$, for constant $\alpha \in (0,1)$.
$TDSP(o,d,t_o)$	The problem of finding a min-cost od-path, given a departure-time $t_o$.
$TDSP(o,\star ,t_o)$	The problem of finding a min-cost paths tree, for given departure-time $t_o$.
TDSP(o, d)	The problem of constructing a succinct representation of min-cost od-paths function.
${\mathtt {TDD}}$	The time-dependent version of Dijkstra’s algorithm.
${\mathtt {TDD}}(o,d,t_o)$	Execution of ${\mathtt {TDD}}$ from o at time $t_o$ to solve $TDSP(o,d,t_o)$.
${\mathtt {TDD}}(o,\star ,t_o)$	Execution of ${\mathtt {TDD}}$ from o at time $t_o$ to solve $TDSP(o,\star ,t_o)$.
${\mathtt {TRAP}}$	The approximation method for minimum-travel-time functions.
${\mathtt {TRAPONLY}}$	The TD-oracle whose preprocessing is based only on ${\mathtt {TRAP}}$ and uses ${\mathtt {RQA}}^+$ as its query algorithm.

Time Complexity of ${\mathtt {RQA}}$ and ${\mathtt {RQA}}^+$

In this section we provide a detailed explanation about the upper bound on the expected time-complexity of the ${\mathtt {RQA}}$ query algorithm, which is also valid, after a few minor modifications, for the ${\mathtt {RQA}}^+$ query algorithm as well.

Recall that the input graph $G=(V,A)$ is sparse: $|A| \in O(|V|)$. We construct a new graph, say ${\tilde{G}}$, having at most $|V|+|A|$ vertices and at most 2|E| arcs, which substitutes each vertex of G with degree greater than 2 as a binary tree with as many leaves as its own degree. All the incoming arcs of v in G now become incoming arcs of the corresponding binary tree’s root. Each outgoing arc of v in G corresponds to a different leaf of the tree, and leads to the root of the tree for the other incident vertex in G. Except for the (outgoing) leaf-arcs which have the same cost as in G, all other tree arcs have zero cost. In ${\tilde{G}}$, we still have exactly the same earliest-arrival-times metric, for all pairs of vertices from V. Moreover, ${\tilde{G}}$ has maximum out-degree at most 2, and it is constructed in time O(|A|). The details of the construction are mentioned in [17]. From now on we assume that the input graph already has maximum out-degree at most 2.

The query algorithm FCA (see [17, Section 4.2]) grows a TDD ball $B_o$ from the vertex-departure pair $(o,t_o)$, until the first landmark, say $\ell _o\in L$ is settled. The ball contains only settled vertices but also “touches” some more vertices via some arc relaxation from a newly settled vertex. We consider the vertices in $B_o$ in increasing Dijkstra-rank order. Clearly, the last settled vertex is $\ell _o$. The “touched” vertices by the ball (after $\ell _o$ in the order) are at most $2|B_o|$, since each vertex has out-degree at most 2. We first consider the position of $\ell _o$ in the Dijkstra-rank order. We assume that each vertex, in that order, reveals its actual type (landmark / non-landmark) as soon as it is chosen by TDD to be settled. This is a Bernoulli trial with success probability $\rho$, independently of the other vertices in the order. Therefore, the position of $\ell _o$ in the order (i.e., the number of settled vertices within $B_o$) is a geometrically distributed random variable with success probability $\rho$ and expectation $\frac{1}{\rho }$. Moreover, for every $k\ge 1$ it holds that $\mathbb {P}\left\{ position(\ell _o) > k\right\} = (1-\rho )^k \le \exp (-\rho k)$. By setting $k = \frac{3\ln (n)}{\rho }$ we have that $\mathbb {P}\left\{ position(\ell _o) > \frac{3\ln (n)}{\rho } \right\} \le \exp (- 3\ln (n)) = n^{-3}$. That is, $B_o$ contains, with probability $1 - n^{-3}$, at most $\frac{3\ln (n)}{\rho }$ settled vertices. As the out-degree in the graph is at most 2, we also know that the total number of settled vertices of $B_o$ and “touched” vertices at the boundary of $B_o$, is no more than $\frac{3}{\rho }$ in expectation, and at most $\frac{3\ln (n)}{\rho }$ with probability $1-n^{-3}$.

The query algorithm ${\mathtt {RQA}}$ (see [17, Section 5]) is recursive: It starts with a TDD ball $B_o$ from $(o,t_o)$, as FCA does. Then, it considers as new ball centers all the (at most $2|B_o|$) “touched” vertices at the boundary of $B_o$, and then continues TDD, separately for each new center, in the residual graph $G - B_o$, until the nearest landmark is discovered. This process is repeated by growing a depth-r recursion tree in a BFS order. Recall that:

• $\forall t_o\ge 0,~\forall w\in V$,

  $\mathbb {P}\left\{ |B[w](t_w)| > \frac{3\ln (n)}{\rho }\right\} = (1-\rho )^{3\ln (n) / \rho } \le \exp (-3\ln (n)) = n^{-3}$

• By applying the Union Bound we have: $\forall t_o\ge 0$,

  $\mathbb {P}\left\{ \exists w\in V: |B[w](t_w)| > \frac{3\ln (n)}{\rho }\right\} \le n\cdot n^{-3} = n^{-2}$

In order to upper-bound the expected time complexity of ${\mathtt {RQA}}$, we consider two mutually exclusive cases:

• All the involved balls have size at most $\beta = \frac{3\ln (n)}{\rho }$. This scenario occurs with probability $1-n^{-2}$. Each ball has at most $2\beta$ boundary vertices, which will be the ball centers of the next level in the recursion tree. Hence, the recursion tree is at most a $2\beta$-ary tree of depth r, therefore it involves $1 + 2\beta + 4\beta ^2 + \cdots (2\beta )^{r} = \frac{(2\beta )^{r+1} - 1}{2\beta -1} \in \mathcal {O}\!\left( \beta ^r\right) \subset \tilde{\mathcal {O}}\!\left( \frac{1}{\rho ^r}\right)$ balls,⁷ each involving at most $3\beta$ (settled or touched) vertices. The execution time of TDD for each of these balls is:

  $$\begin{aligned}&\mathcal {O}\!\left( \beta \log (\beta )\log \log (K_{\max })\right) \\&\quad = \mathcal {O}\!\left( \frac{\log (n)}{\rho }\cdot [\log \log (n)+\log (1/\rho )]\cdot \log \log (K_{\max })\right) \\&\quad \subset \tilde{\mathcal {O}}\!\left( \frac{1}{\rho }\right) \end{aligned}$$

  Therefore, in the worst-case, the expected time complexity of ${\mathtt {RQA}}$ in this scenario is at most

  $$\begin{aligned} \mathcal {O}\!\left( \left( \frac{\log (n)}{\rho }\right) ^{r+1} \cdot [\log \log (n)+\log (1/\rho )] \cdot \log \log (K_{\max }) \right) \subset \tilde{\mathcal {O}}\!\left( \frac{1}{\rho ^{r+1}} \right) \end{aligned}$$

• At least one of the involved balls has size greater than $\beta$. This scenario occurs with probability $n^{-2}$. We then simply treat each ball as if it covers the entire graph. In the worst case there may be at most n balls. Therefore, the overall expected time complexity of ${\mathtt {RQA}}$ in this scenario is at most

  $$\begin{aligned} \mathcal {O}\!\left( n^2\cdot \log (n)\cdot \log \log (K_{\max }) \right) \subset \tilde{\mathcal {O}}\!\left( n^2\right) \end{aligned}$$

Now, we can upper-bound the expected time-complexity of ${\mathtt {RQA}}$ as follows:

$$\begin{aligned}&{\mathbb {E}\left\{ Q_{{\mathtt {RQA}}}\right\} }\\&\quad \le (1 - n^{-2}) \cdot \mathcal {O}\!\left( \left( \frac{\log (n)}{\rho }\right) ^{r+1} \cdot [\log \log (n)+\log (1/\rho )] \cdot \log \log (K_{\max }) \right) \\&\qquad + n^{-2} \cdot \mathcal {O}\!\left( n^2\cdot \log (n)\cdot \log \log (K_{\max })\right) \\&\quad \subset \tilde{\mathcal {O}}\!\left( \frac{1}{\rho ^{r+1}} \right) \end{aligned}$$