Oracles for Distances
Avoiding a Link-failure
C. Demetrescu
(U. Rome La Sapienza)
V. Ramachandran
(U. Texas Austin)
R.A.Chowdhury
(U. Texas Austin)
M. Thorup
(AT&T Research)
The distance sensitivity problem
Given a weighted directed graph G=(V,E,w),
construct a data structure (oracle) that
supports queries of the kind:
Query(x,y,u,v): what is the distance xy in G
avoiding edge (u,v)?
x
u
v
y
Related work
Transitive Closure in Acyclic Digraphs
- V. King, G. Sagert, STOC’99
Distances between fixed x,y avoiding an edge
- J. Hershberger and S. Suri, FOCS 2001
Minimum Spanning Tree
- E. Nardelli et al., Algorithmica 40(2), 2004
Motivating scenario
Network where failures
happen quite rarely
Motivating scenario
Network where failures happen quite rarely
Dynamic
Solution
Router SP queries
Time
~ 2
O(n )
Updated routing table
Oracle
Solution
Router SP queries
Time
Oracle
Simple-minded oracle
Keep a table of size O(n3)
d[x,y,1]
d[x,y,2]
...
d[x,y,3]
d[x,y,n-1]
x
v
x
u
x
x
y
v
u
y
v
u
y
v
y
...
d[x,y,0]
 Query O(1)
x
Using cubic space is prohibitive!
u
y
Our results
Space
Query
Oracle 1
O(n2 log n)
O(1)
Oracle 2
O(n2.5)
O(1)
n = num. vertices
Preproc.
~
O(mn2)
~
O(mn1.5)
m = num. edges
Oracle 1: data structure
Keep four tables of size O(n2 log n): sl, sr, dl, dr
sl[x,y,0]
sl[x,y,1]
sl[x,y,2]
y
x
y
x
y
x
y
sl[x,y,log n]
...
...
sl[x,y,3]
x
x
1
1
2
4
y
Oracle 1: data structure
Keep four tables of size O(n2 log n): sl, sr, dl, dr
sr[x,y,0]
sr[x,y,1]
sr[x,y,2]
y
x
y
x
y
x
y
sr[x,y,log n]
...
...
sr[x,y,3]
x
x
4
2
1
1
y
Oracle 1: data structure
Keep four tables of size O(n2 log n): sl, sr, dl, dr
dl[x,y,0]
dl[x,y,1]
dl[x,y,2]
y
x
y
x
y
x
y
dl[x,y,log n]
...
...
dl[x,y,3]
x
x
1
1
2
4
8
y
Oracle 1: data structure
Keep four tables of size O(n2 log n): sl, sr, dl, dr
dr[x,y,0]
dr[x,y,1]
dr[x,y,2]
y
x
y
x
y
x
y
dr[x,y,log n]
...
...
dr[x,y,3]
x
x
8
4
2
1
1
y
Querying the oracle…
Oracle 1: answering queries
2i-1
1
dl[x,y,i]
x
l
min
2
u
v
u
v
y
r
2j-1
d[x,l’]+sl[l’,y,j]
x
l’
l
y
2k-1
3
sr[x,r’,k]+d[r’,y]
x
u
v
r
r’
y
Oracle 2: data structure
Keep three tables of size O(n2.5): dl, dr, dc
dl[x,y,0]
dl[x,y,1]
dl[x,y,2]
y
x
y
x
y
x
y
dl[x,y,√n]
...
...
dl[x,y,3]
x
x
y
√n
Oracle 2: data structure
Keep three tables of size O(n2.5): dl, dr, dc
dr[x,y,0]
dr[x,y,1]
dr[x,y,2]
y
x
y
x
y
x
y
dr[x,y,√n]
...
...
dr[x,y,3]
x
x
y
√n
Oracle 2: data structure
Keep three tables of size O(n2.5): dl, dr, dc
dc[x,y,0]
dc[x,y,1]
y
x
y
x
y
dc[x,y,√n]
...
...
dc[x,y,2]
x
x
y
<√n
<√n
<√n
√n
Oracle 2: answering queries
1
<√n
dc[x,y,...]
x
l
u
v
r
y
<√n
2
d[x,l]+dl[l,y,...]
x
l
u
v
y
<√n
3
dr[x,r,...]+d[r,y]
x
u
v
r
y
Computing distances avoiding sub-paths
x
Distances from x to every y
excluding a band of edgedisjoint sub-paths can be
computed in Õ(m)
Band of edge-disjoint
sub-paths
y
Oracle 2: constructing table dl (and dr)
x
n bands
from first
levels
y
 O(mn) per SP tree  O(mn1.5) total
A combinatorial property on trees
<n internal nodes with
outdegree >1 remain
All but <n
leaves disappear
Remove
subtrees with
<n nodes
Oracle 2: constructing table dc
may be
> n
<n bands obtained
by cutting at nodes
with degree >1
n bands obtained by
cutting at regular
intervals
Red+Blue  < 2n bands of edge-disjoint sub-paths
and of height < n  O(mn1.5) total
Conclusions
We have shown that there exists a data
structure of size O(n2 log n)
that supports distance sensitivity
queries in O(1) time
We can deal with node failures within
the same bounds
Can we improve construction time?
Can we support multiple
simultaneous failures?