Transcript presentation3

Approximate Distance Oracles
Mikkel Thorup and Uri Zwick
Presented By
Shiri Chechik
Approximate Distance Oracles
Consider a graph G=(V,E).
 An approximate distance oracle with a
stretch k for the graph G is
a data-structure that can answer an
approximate distance query for any
two vertices with a stretch of at most
k.
 For every u,v in V the data structure
returns in “short time” an approximate
distance d’ such that:
dG(u,v)  d’  k· dG(u,v) .

Approximate Distance Oracles
Stretch
Query
time
64k
kn1/k
2k+
kn1/k
2k-1
k
Space
Preproc.
time
Reference
AwerbuchBergerCowen-Peleg
‘93
kn1+1/k
kmn1/k
Cohen ‘93
ThorupConstant
time!is Zwick ‘01
Thisquery
tradeoff
essentially optimal !
Slide from Uri Zwick
Spanners - Formal Definition
Consider a graph G=(V,E) with
positive edge weights.
 A subgraph H is a k-spanner of G if
for every u,v in V:

dH(u,v)  k·dG(u,v) .
Spanners - Example
v
Spanners - Equivalent Definition

A subgraph H is a k-spanner of G if
for every edge (u,v) in E:
dH(u,v)  k· w(u,v) .
x
y
Spanners for General graphs
Theorem
 One can efficiently find a
(2k-1)-spanner with at most n1+1/k
edges.
Spanners for General graphs
Girth Conjecture (Erdös and others):
 There are n-vertex graphs with
Ω(n1+1/k) edges that have girth > 2k.
Known for k=1,2,3,5.
Distance Oracles - Construction
Preprocessing Phase
First build a hierarchy of
centers, A0,…, Ak
 A0 V, Ak 
Ai sample(Ai-1, n-1/k)

Distance Oracles - Construction
Preprocessing Phase
A0 =
A1 =
A2 =
Ak =
A hierarchy of centers
A0V ; Ak  ;
Ai sample(Ai-1,n-1/k) ;
Slide from Uri Zwick
Distance Oracles - Construction
Preprocessing Phase
Notations
 pi(v) is the closest node to v in Ai
 For each w  Ai\Ai+1
◦ C(w)  {v| δ(v,w) < δ(v,pi+1(v))}
A0=
A1=
A2=
Clusters
w
C ( w )  {v V |  ( w, v )   ( Ai 1 , v )} , w  Ai  Ai 1
Slide from Uri Zwick
Bunches (inverse clusters)
w  B(v )  v  C ( w )
C ( w )  {v  V |  ( w , v )   ( Ai 1 , v )}
,
if w  Ai  Ai 1
{ w  Ai  Ai 1 |  ( w , v )   ( Ai 1 , v ) }
B(v ) 
i
Slide from Uri Zwick
Distance Oracles - Example
V
P1(V)
Distance Oracles - Example







A0 = {v1, v2, v3, v4}
A1 = {v2, v3}
A2 = {v3}
A3 = {}
V3
1
2
V2
C(v1)= {v1,v4}, C(v4)= {v4}
C(v2)= {v2, v1}
C(v3)= {v1, v2, v3, v4}
V4
1
1.5
V1
Distance Oracles - Construction
Preprocessing Phase
Data structures
 For every v  V
◦ p1(v),…,pk-1(v) and the distance
from v to pi(v).
◦ C(v) (hash table) and the distance
from v to every u in C(v).
Distance Oracles
Lemma: E[|B(v)|]≤kn1/k
|B(v)Ai| is stochastically
dominated by a geometric
random variable with parameter
p=n-1/k.
Slide from Uri Zwick
Distance Oracles
Lemma
 For
every two nodes u and v,
there exists a node w such
that
◦ u,v  C(w)
◦ The distance from u to w and from
v to w is at most k·d(u,v)
Distance Oracles - Construction
Query Phase
Distance Oracles - Construction
Query Phase
P3(v)
P2(u)
P1(v)
2>
<
u

v
<3
Distance Oracles - Example
What is δ(v4, v1)?
 Is v1 C(v4)?
 w = p1 (v1) = v2
 Is v4 C(v2)?
 w = p2(v4) = v3
 Is v1 C(v3)? – Yes
V3
1
2
V2
V4
1
1.5
V1
C(v1)= {v1,v4}, C(v4)= {v4}
C(v2)= {v2, v1}
C(v3)= {v1, v2, v3, v4}
Distance Oracles - Properties
Thorup and Zwick (2005)

Consider a node v  C(w), every
node on a shortest path from v
to w also belongs to C(w).
x  Ai+1
v
y
w
Distance Oracles - Properties
Thorup and Zwick (2005)

v belongs to C(pi(v)) for every
0≤ i ≤k-1.
Distance Oracles
From each cluster, construct a tree
T(w) containing shortest path.
v
u
w
Distance Oracles
 The
union of all these trees
is a (2k-1)-spanner with
O(kn1+1/k) edges.