Incremental Approximate Single-Source Shortest Paths with Predictions

Data structures augmented with predictions have demonstrated empirical success in key applications such as indexing [27, 13, 11], caching [26, 33], Bloom filters [38, 46], frequency estimation [24], page migration [25], routing [8].

Initial theoretical work on data structures with predictions focused on improving their space complexity or competitive ratio, e.g. learned filters [46, 38, 3] and count-min sketch [24, 16] on stochastic learned distributions. Several papers have since used predictions to provably improve the running time of dictionary data structures, e.g. learned binary-search trees [30, 10, 49, 14]. McCauley et al. [36] presented the first “ideal” data structures with prediction for the list-labeling problem [36]. They use a “prediction-decomposition” framework to obtain their bounds and extend the technique to maintain topological ordering and perform cycle detection in incremental graphs with predictions [37].

We review the state-of-the-art deterministic worst-case algorithms for the incremental $(1+ϵ)$ SSSP problem.

The best-known deterministic algorithm for dense graphs is by Gutenberg et al. [41] with total update time $\tilde{O}(n^2\log W/{ϵ}^{O(1)})$, which is nearly optimal for very dense graphs. For sparse graphs, Chechik and Zhang [9] give an algorithm with total time $\tilde{O}(m^{5/3}\log W/ϵ)$, which is improved by Kyng et al. [28] to a total time $\tilde{O}(m^{3/2}\log W/ϵ)$; this is the best-known deterministic algorithm for sparse graphs. Note that many of these solutions use the ES-tree data structure [44] as a key building block. The ES-tree can maintain exact distances in an SSSP tree for weighted graphs with total running time $O(mnW)$ [23], where $W$ is the ratio of the largest to smallest edge weight. The ES-tree can be used to maintain $(1+ϵ)$-approximate distances in total update time $\tilde{O}(mn\log W/ϵ)$ for incremental/decremental directed SSSP; see e.g. [4, 5, 34].

This paper shows that even modestly accurate predictions can be leveraged to circumvent these high (polynomial) worst-case update costs in incremental SSSP.

For the approximate incremental APSP problem without predictions, Bernstein [5] gave an algorithm that has nearly-optimal total runtime $O(nm{\log }^4(n)\log (nW)/ϵ)$ and $O(1)$ look-up time.

Peng and Rubinstein consider generally how incremental or decremental algorithms can be turned into fully dynamic algorithms [39].

Our algorithm recursively divides the sequence of edge inserts in half, starting with the entire sequence of edge inserts $\{e_1,\mathrm{\dots },e_m\}$, and recursing until the sequence contains a single edge.

Consider a sequence $\{e_{\mathrm{\ell }},\mathrm{\dots },e_r\}$, which we denote by $[\mathrm{\ell },r]$. We divide this interval into two equal halves: $[\mathrm{\ell },x],[x,r]$.

The observation behind our algorithm is the following. Let’s say we calculate the distance to all vertices at time $x$. Consider a vertex $v$ that is in the same bucket at $\mathrm{\ell }$ and $x$. Since the distance to $v$ is non-increasing as new edges arrive, $v$ must be in this bucket throughout the interval, and we do not need to continue calculating its distance. Therefore, we should remove $v$ from the recursive call for the interval $[\mathrm{\ell },x]$. Similarly, if $v$ is in the same bucket at $x$ and $r$, then we should remove $v$ from $[x,r]$.

If we are successful in removing vertices this way, we immediately improve the running time. Each vertex $v$ is included in an interval $[\mathrm{\ell },r]$ if and only if it shifts from one bucket to another between $\mathrm{\ell }$ and $r$. Thus, each time $v$ shifts buckets, it is included in at most $\log m$ intervals. This means that each vertex is included in $O(\log m\log (nW)/ϵ)$ intervals.

Let’s assume that for an interval $[\mathrm{\ell },r]$, we can run Dijkstra’s algorithm for the midpoint $x$ in time (ignoring log factors) proportional to the number of edges that have at least one endpoint included in the interval $[\mathrm{\ell },r]$. Since each vertex contributes to the running time of $\text{polylog}(nmW)/ϵ$ different subproblems, we can sum to obtain $\tilde{O}(m\log W/ϵ)$ total cost to calculate the shortest path to every vertex in every subproblem.

Let us discuss in more detail how to “remove” a vertex from a recursive call. We do not remove vertices from the graph; instead, we say that a vertex is dead during an interval $[\mathrm{\ell },r]$ if its distance bucket does not change during the interval, and alive otherwise. Each edge $(u,v)$ is alive if and only if $v$ is alive.

For each time $x$ which is the midpoint of an interval $[\mathrm{\ell },r]$, consider building a graph $G_x^{\prime }$ consisting of all alive vertices and edges in $[\mathrm{\ell },r]$. If $(u,v)$ is alive, but $u$ is dead, we also add $u$ to $G_x^{\prime }$. Now, the time required to run Dijkstra’s algorithm on $G_x^{\prime }$ is roughly proportional to the number of edges in $G_x^{\prime }$ as we desired, but the distances it gives are not meaningful – in fact, $s$ may not even be in $G_x^{\prime }$.

To solve this problem, we observe that we already know (approximately) the distance to any dead vertex $u$: we marked $u$ as dead because its distance bucket does not change from $\mathrm{\ell }$ to $r$. Thus, we add $s$ to $G_x^{\prime }$; then, for each alive edge $(u,v)$ where $u$ is dead, instead of adding $u$ to $G_x^{\prime }$, we add an edge from $s$ to $v$ with weight equal to the rounded distance from $s$ to $u$ from the previous recursive call plus $w(u,v)$. Running Dijkstra’s algorithm on $G_x^{\prime }$ now gives (ostensibly) meaningful distances from $s$.

We calculate the distance to each vertex in $G_x^{\prime }$, round the distance up to obtain its bucket, and then recurse (marking vertices dead as appropriate) on $[\mathrm{\ell },x]$ and $[x,r]$.

Unfortunately, the above method does not quite work, as the error accumulates during each recursive call.

For an interval $[\mathrm{\ell },r]$ with midpoint $x$, we use the terms recursive call $[\mathrm{\ell },r]$ and recursive call $x$ interchangeably. For a recursive call $x$, the shortest path to $v$ may begin with an edge $(s,v^{\prime })$ (for some dead vertex $v^{\prime }$) weighted according to the bucket of $v^{\prime }$. The bucket of $v^{\prime }$ was calculated by rounding up the length of the shortest path to $v^{\prime }$ in some graph $G_y^{\prime }$ at time $y$; the length of this path again was also rounded up, and so on.

In other words, since the weight of each edge from $s$ to a dead vertex $v^{\prime }$ is based on the bucket of $v^{\prime }$, it has been rounded up to the nearest power of $1+ϵ$. Thus, each recursive call loses a $1+ϵ$ approximation factor in distance.

To solve this, we note that the recursion depth of our algorithm is ${\log }_{2}m$. Thus, we split into finer buckets: rather than rounding up to the nearest power of $1+ϵ$, we round up to the nearest power of $1+ϵ/{\log }_{2}m$. Thus, the total error accumulated over all recursive calls is ${(1+ϵ/{\log }_{2}m)}^{{\log }_{2}m}\le 1+ϵ+{ϵ}^2$ (see Section 2); decreasing $ϵ$ slightly gives error $1+ϵ$.

Rounding buckets up to the nearest power of $1+ϵ/\log m$ changes our running time analysis: most critically, each vertex now changes buckets ${\log }_{1+ϵ/\log m}nW=\mathrm{\Theta }(\log (nW)\log m/ϵ)$ times.

To start, let’s give a simple algorithm that uses predictions that contain error. Let $Ham(\sigma ,\widehat{\sigma })$ be the Hamming distance between $\sigma$ and $\widehat{\sigma }$ – in other words, the number of edges whose predicted arrival time was not exactly correct in $\widehat{\sigma }$. We give an algorithm that runs in $\tilde{O}(m(1+Ham(\sigma ,\widehat{\sigma }))\log W/ϵ)$ time.

The main idea behind this algorithm is to update the sequence of predictions $\widehat{\sigma }$ as edges come in. At time $t$, an edge $e$ arrives; if $e$ arrived at $t$ in $\widehat{\sigma }$, the algorithm does nothing – the predictions created by running the offline algorithm on $\widehat{\sigma }$ took $e$ arriving at $t$ into account. If $e$ did not arrive at $t$ in $\widehat{\sigma }$, then the algorithm creates a new $\widehat{\sigma }$, replacing the edge arriving at $t$ with $e$. The algorithm then reruns the offline algorithm on the new $\widehat{\sigma }$ in $\tilde{O}(m\log W/ϵ)$ time.

Since we run the offline algorithm (in $\tilde{O}(m\log W/ϵ)$ time) each time an edge was predicted incorrectly, we immediately obtain $\tilde{O}(m(1+Ham(\sigma ,\widehat{\sigma }))\log W/ϵ)$ time.

Ideally, we would not rebuild from scratch each time an edge is predicted incorrectly – we would like the running time to be proportional to how far an edge’s true arrival time is from its predicted arrival time.

Our final algorithm improves over the warmup Hamming distance algorithm in two ways. First, it updates the predicted sequence $\widehat{\sigma }$ more carefully. Second, it only rebuilds parts of the recursive calls of the offline algorithm: specifically, only intervals that changed as $\widehat{\sigma }$ was updated.

First, let’s describe how to update $\widehat{\sigma }$. As before, when an edge $e$ arrives at time $t$, if $e$ was predicted to arrive at $t$ in $\widehat{\sigma }$ the algorithm does nothing. If $e$ was predicted to arrive at time $t^{\prime }$ in $\widehat{\sigma }$, the algorithm modifies $\widehat{\sigma }$ by inserting $e$ at time $t$ (shifting all edges after $t$ down one slot), and deleting $e$ at time $t^{\prime }$ (shifting all edges after $t^{\prime }$ up one slot). If $e$ is not predicted in $\widehat{\sigma }$, the algorithm only inserts $e$ at time $t$, shifting subsequent edges down one slot.

The only entries in $\widehat{\sigma }$ that change are those between $t$ and $t^{\prime }$ (inclusive). Therefore, we only need to recalculate $G^{\prime }$ for times between $t$ and $t^{\prime }$.

Finally, we update the distance array $D$. The algorithm greedily updates $D$ during the above rebuilds to maintain the invariant that $D[i]$ stores the estimated distance ${\widehat{d}}^t(v_i)$, which as discussed in Section 2, is a $(1+ϵ)$ approximation for $d^t(v_i)$.

For any edge $e$ that appears at time $\text{index}(e)$ in $\sigma$ and time $\widehat{\text{index}}(e)$ in $\widehat{\sigma }$, we define ${\eta }_e=|\text{index}(e)-\widehat{\text{index}}(e)|$. If $e$ does not appear in $\widehat{\sigma }$ then ${\eta }_e=|m+1-\text{index}(e)|$. Let $\eta$ be the maximum error: $\eta ={\max }_{e\in \sigma }{\eta }_e$.

We show that, after the initial run of the offline algorithm, an edge $e$ causes a rebuild of a graph $G_t^{\prime }$ only if $t$ is between its predicted arrival time $\widehat{\text{index}}(e)$ and its actual arrival time $\text{index}(e)$. This means that each $G_t^{\prime }$ can only be rebuilt $O(\eta )$ times. Since the total time to build all $G_t^{\prime }$ is $\tilde{O}(m\log W/ϵ)$, the total time to rebuild all $G_t^{\prime }$ $O(\eta )$ times is $\tilde{O}(m(1+\eta )\log W/ϵ)$.

With a more careful analysis, we can get the best of the Hamming analysis and the max error analysis. For any $\tau$, let $\text{HIGH}(\tau )$ be the set of edges with error more than $\tau$. For all edges with error more than $\tau$, we may (in the worst case) rebuild the entire interval $\{1,\mathrm{\dots },m\}$, for total cost $\tilde{O}(m|\text{HIGH}(\tau )|\log W/ϵ)$. For all edges with error at most $\tau$, the total rebuild cost is, as above, $\tilde{O}(m\tau \log W/ϵ)$. Thus, we obtain total cost $\tilde{O}\left(m(1+{\min }_{\tau }\{\tau +|\text{HIGH}(\tau )|\})\log W/ϵ\right)$.

For any $x$, let $m_x$ be the number of alive edges in $G_x$. The algorithm maintains a list of all alive edges at each time $x$.

We now describe how to find the alive vertices and edges in $G_x$, where $x$ is the midpoint of $[\mathrm{\ell },r]$. Note that if an edge $(u,v)$ is alive in $G_x$, then its head $v$ must be alive in $G_x$, which in turn implies that $v$ is alive in $G_{\mathrm{\ell }}$ and $G_r$. Since $(u,v)$ has arrived before time $r$, it is alive in $G_r$. Therefore the alive edges in $G_x$ are a subset of the alive edges in $G_r$. To obtain the list of alive edges in $G_x$, the algorithm iterates over the alive edges in $G_r$ in $O(m_r)$ time, and removes the edges that either arrived after time $x$, or whose head node has the same estimated distance in both $G_{\mathrm{\ell }}$ and $G_r$. While doing this, the algorithm additionally updates if each vertex is alive or not in $G_x$ in $O(m_r)$ time.

From this, the algorithm constructs $G_x^{\prime }$ in $O(m_r)$ time, and runs Dijkstra’s algorithm in $O(m_r\log n)$ time.

To obtain the $L_v(i)$ values, initially, all the entries of $L_v$ are empty. At each time $x$, when we are calculating the distance estimate ${\widehat{d}}^x(v)$ for an alive node $v$, we update $L_v$: suppose . If $L_v(i)$ is empty or , we set $L_v(i)$ to be $x$. Otherwise, $L_v(i)$ remains unchanged. In the end, the algorithm processes each of the lists, and for any empty $L_v(i)$, the algorithm sets it to be equal to the last non-empty entry of $L_v$ before $L_v(i)$.

Our algorithm dynamically maintains the predicted sequence of edge inserts by changing $\widehat{\sigma }$ online. Specifically, after the $t$th edge arrival, the algorithm will construct a new prediction which we refer to as ${\widehat{\sigma }}_t$. Initially, ${\widehat{\sigma }}_0=\widehat{\sigma }$. We call the sequence ${\widehat{\sigma }}_t$ the updated prediction. Intuitively, the algorithm modifies the updated prediction after each edge arrival based on which edge actually arrives.

For each edge $e$, let ${\widehat{\text{index}}}_t(e)$ be the position of $e$ in ${\widehat{\sigma }}_t$. Let $\text{index}(e)$ denote the position of $e$ in $\sigma$ (i.e. the true time when $e$ arrives). If $e\notin {\widehat{\sigma }}_t$, then we define ${\widehat{\text{index}}}_t(e):=m+1$.

Our algorithm updates the sequence of edges to agree with all edges seen so far. In other words, at time $t$, the algorithm maintains that for all edges $e$ that arrive by $t$ in $\sigma$, ${\widehat{\text{index}}}_t(e)=\text{index}(e)$.

Since the online algorithm continuously updates the result of the offline approach, it stores information to help it navigate the result of the offline algorithm.

Recall that the offline algorithm stores, for each time $t$, the set of vertices and edges alive at time $t$, as well as a distance estimate ${\widehat{d}}^t(v)$ for any vertex $v$ alive at time $t$. The online algorithm maintains exactly the same information. We will see that the algorithm updates these estimates continuously as the updated prediction changes.

First, let us describe the preprocessing performed by the algorithm before any edges arrive. The algorithm sets $D[i]=\mathrm{\infty }$ for all $i$, except for $D[1]=0$, which represents the source. Then, the algorithm runs the offline algorithm from Section 4 on $\widehat{\sigma }$. By running the offline algorithm, the algorithm will store ${\widehat{d}}^t(v)$ for all times $t$ and all nodes $v$ alive at time $t$.

Now, let us describe how the algorithm runs after the $t$th edge is inserted. At each time $t$, the algorithm rebuilds a subset of all the subproblems. These rebuilds update the precomputed ${\widehat{d}}^t(v)$. When a subproblem is rebuilt, all of its descendants are rebuilt as well. The rebuilding procedure is formally described below.

Let $e_t$ be the edge that arrives at time $t$, and let $t^{\prime }={\widehat{\text{index}}}_{t-1}(e_t)$, i.e., $t^{\prime }$ is the predicted arrival time for $e_t$ in the updated predictions immediately before it arrives. Note that since the first $t-1$ edges of $\sigma$ and ${\widehat{\sigma }}_{t-1}$ are the same, we always have $t^{\prime }\ge t$ (assuming the edges in the input sequence are distinct).

First, we describe how the algorithm updates ${\widehat{\sigma }}_{t-1}$ to get ${\widehat{\sigma }}_t$.

• $\mathrm{■}$

  If $t=t^{\prime }$, i.e., the position of $e_t$ is predicted correctly at the time it is seen, then set ${\widehat{\sigma }}_t:={\widehat{\sigma }}_{t-1}$.

• $\mathrm{■}$

  If $t\ne t^{\prime }$ and $t^{\prime }\le m$; that is, $e_t$ is predicted to arrive at a later time. In this case, the algorithm moves $e_t$ from position $t^{\prime }$ to position $t$ in ${\widehat{\sigma }}_{t-1}$, and shifts everything between $t$ and $t^{\prime }$ one slot to the right to obtain ${\widehat{\sigma }}_t$.

• $\mathrm{■}$

  If $t\ne t^{\prime }$ and $t^{\prime }=m+1$; that is, at time $t-1$, $e_t$ is not in the predicted sequence. In this case, the algorithm inserts $e_t$ in position $t$, shifts the rest of the sequence one slot to the right, and truncates the predicted sequence to length $m$ to obtain ${\widehat{\sigma }}_t$.

Next, the algorithm rebuilds subproblems. Recall that the algorithm given in Section 4 is recursive; each of its recursive calls can be represented by a node in the recursion tree.

To rebuild a subproblem $[\mathrm{\ell },r]$, the offline algorithm is called on $[\mathrm{\ell },r]$ using the updated prediction ${\widehat{\sigma }}_t$. The rebuild makes recursive calls as normal. Any time a subproblem with midpoint $x$ is rebuilt, the value of ${\widehat{d}}^x(v)$ is updated based on the rebuild for all alive vertices $v$.

Let $[{\mathrm{\ell }}_M,r_M]$ be the largest subproblem with ; then the algorithm rebuilds $[{\mathrm{\ell }}_M,r_M]$. As mentioned above, all descendants of $[{\mathrm{\ell }}_M,r_M]$ will be recursively called, and therefore rebuilt as well. In other words, the algorithm rebuilds all the subproblems $[\mathrm{\ell },r]$, with , and all of their descendants from top to bottom (so in the first case, no subproblem gets rebuilt). See Figure 2 for an illustration. Let $\text{rebuild}(t)$ be the set of all times $t^{\prime \prime }$ such that $t^{\prime \prime }\in [\mathrm{\ell },r]$ for some $[\mathrm{\ell },r]$ rebuilt at time $t$. If no subproblem is rebuilt at time $t$, we define $\text{rebuild}(t):=\{t\}$ to ensure that $t$ is always in $\text{rebuild}(t)$.

Finally, the algorithm must update the array $D$ containing the estimated distance to each vertex. When a new edge is inserted, some of the entries in $D$ need to be overwritten, as their estimated distance might have changed. At each time $t$, we want to have $D[i]={\widehat{d}}^t(v_i)$ for all $i$. To do so, the algorithm does the following for each time $t^{\prime }\in \text{rebuild}(t)$, where $t^{\prime }\le t$, in sorted order. The algorithm iterates through all alive vertices $v_i$ in $G_{t^{\prime }}$, and sets $D[i]={\widehat{d}}^{t^{\prime }}(v_i)$. As explained in Section 4, with some additional bookkeeping, the algorithm can also return the shortest path to each node $v_i$.