Transcript Constant Average Distortion Embedding into lp

On Space-Stretch Trade-Offs:
Upper Bounds
Ittai Abraham, Cyril Gavoille, Dahlia Malkhi
Plan

Main result



Name independent routing scheme with
stretch O(k) and memory O(n1/k polylog(n))
Related work
Main technical contributions:



Sparse Dense decomposition
Routing for “dense areas”
Routing for “sparse areas”
Space-Stretch Trade-Off


Distributed routing scheme: Node that knows the
label of a target node can send a message that
will be routed to the target node
Complexity measures:



Stretch: the ratio between the cost of the path taken
by the routing protocol and the cost of a minimum
cost path from source to destination.
Memory: the number of bits stored in each node.
The Space-Stretch Trade-Off: what stretch with
O(n1/k polylog(n)) memory?
Main Result



Compact Routing Scheme
Name Independent model
Parameter k:


Each node stores O(n1/k polylog(n)) bits
Stretch is O(k)
Main Technical Contribution
A sparse-dense decomposition


Combines two different routing techniques
1.
2.

Sparse covers (used in “dense areas”)
Random sampling (used in “sparse areas”)
A tree routing scheme used in “sparse
areas”
Related Work

Random Sampling techniques





With O(n1/k polylog(n)) memory
[ABLP 89,90] O(k2 9k)
[ACLRT 03] O(k2 2k)
[L 04] for trees O(2k), single source O(k)
Sparse Cover techniques




With O(log(D) n1/k polylog(n)) memory
[AP 92] O(k2)
[ACLRT 03] O(k2)
[AGM 04] O(k)
Awerbuch & Peleg’s
routing scheme [AP92]



Let D be the network diameter
Let s be a source and t a target
For i=1 to log(D)




Search for t in the ball B(s,2i)
Suppose cost of search is O(z 2i)
So if d(s,t)≈2j then total cost will be
O(z 21)+O(z 22)+…+O(z 2j)=O(z 2j)
Stretch is O(z)
Awerbuch & Peleg’s
sparse covers [AP90]
For i=1 to log(D)

i)
Search
for
t
in
the
ball
B(s,2
Search for t in the cluster containing B(s,2i)

For i=1 to log(D): build a sparse cover for 2i

1.
2.
3.
(Small Diameter) Each cluster has diameter O(k 2i)
(Sparse): Each node belongs to O(k n1/k) clusters
(Cover): Each node x belongs to a cluster that
contains the ball B(x,2i)
Memory is O( log(D) n1/k polylog(n))
On each cluster, build a tree routing scheme




[AP 90] search cost is O(k2 2i) (similar to [L 04])
[AGM 04] improves to O(k 2i)
Awerbuch & Peleg’s
sparse covers [AP90]
(sparse):
Each node belongs to O(k n1/k) clusters
(Cover): Each node x belongs to
a cluster that contains the ball
B(s,2i)
2i
(Small Diameter): Diameter of
each cluster is O(k 2i)
s
Tree routing on cluster: If target
is in B(s,2i) then its found using a
tree routing scheme, otherwise
“not found” is reported
[AGM 04] In any case, cost of tree
searching is O(k 2i)
Sparse-Dense Decomposition
Standard technique: double the radius each iteration
Sparse-Dense: double both the
radius and the node count each iteration:
(always choose radii that are powers of two)
There are at most O(log n) levels
Diam=2i
Nodes=x
s
Dense:
Diam=2i+1
Nodes > 2x Sparse:
Diam > 2i+1
Nodes = 2x
Sparse-Dense Decomposition
For a parameter k:
 Sparse-Dense: double the radius and
increase the node count by a factor of n1/k
(always choose radii that are powers of two)
 Hence each node has an increasing
sequence of at most k radii: a1,…,ak (each


is a power of two)
Definition:


Level i is dense if ai+1 < 8 ai
Level i is sparse if ai+1 ≥ 8 ai
Sparse-Dense Decomposition

For dense levels, use sparse cover base
techniques



Each node participates in only O(log n) scales
of sparse covers
In order to route from s to t we need all nodes
to participate in the same scale of the sparse
cover
For sparse levels, use random sampling
based techniques

Requires a new tree routing scheme
Dense Levels
Goal: if i is a dense level for u then all nodes in
B(u,2i-1) participate in the scale 2i sparse cover
 Suppose radius is only doubled, hence
|B(u,2i+1)|>2|B(u,2i)|
 Level i is a dense level for u
 For any v in B(u,2i-1):




B(v,2i-1) is contained in B(u,2i)
B(v,2i+3) contains B(u,2i+1)
So |B(v,2i+3)| > |B(u,2i+1)| > 2|B(u,2i)| > 2|B(v,2i-1)|
Either level {i-1,i,i+1} must be a dense level for v
Dense Levels
• If i is a dense level for u and vB(u,2i-1),
then {i-1,i,i+1} is a dense level for v
• Solution: Each node v participates in the
sparse cover of scale 2r if r{i+2,…,i-2}
where i is a dense level for node v
• Hence if i is a dense level for u then all
nodes in B(u,2i-1) participate in the scale 2i
sparse cover
Sparse Levels

To double the node count, suppose radius must
be multiplied by at least 8 (maybe much more),
hence i’>i+2 and |B(u,2i’)| ≥ 2|B(u,2i)|



Suppose there are 2j nodes in B(u,2i)
Random sampling solution: Choose
j-landmarks with probability (log n)/2j



So |B(u,2i’-1)| < 2|B(u,2i)|
B(u,2i) contains a j-landmark with high probability
B(u,2i’-1) contains only O(log2 n) j-landmarks with high
probability
Trees: For every j, each node participates in the
tree of the O(log2 n) closest j-landmarks
Sparse Levels:
name-independent tree routing


Hence all nodes in B(u,2i’-1) participate in
a tree T rooted in B(u,2i)
Unfortunately, cannot apply standard
name-independent tree routing techniques


[AGM 04] requires bounded diameter and
small edges
[ABLP 89, AP 90, L 04] stretch O(k), but if
target is not found then the cost is (k diam(T))

Diam(T) may be very large, relative to 2i
Sparse Levels:
name-independent tree routing

Need tree routing scheme:




Let t(j) be the 2j closest nodes of the tree
Build a variation of name-independent tree
routing scheme for each t(j+1):





Finds target with stretch O(k)
Reports target not in B(u,2i) with cost O(k 2i)
Searches nodes in t(j+1) by routing only in t(j)
Finds target with stretch O(k)
Reports target not in t(j+1) with cost O(k diam(t(j)) )
Since |B(u,2i’-1)| < 2|B(u,2i)| = 2j+1 then searching
in B(u,2i’-1) is contained in t(j+1) which is done by
routing in t(j) which is contained in B(u,2i)
Cost is O(k diam(t(j)) ) = O(k 2i), stretch is O(k)
Conclusions


Obtain similar results for strongly connected
directed graphs and roundtrip routing [CLR 04]
Combing partition based techniques with
random sampling techniques found useful



Improved routing schemes for graphs with low
doubling dimension [AGGM 06, KRX 06]
Advances in metric space embedding theory [KLMN
04, ABN 06]
Open questions: exact constants



What is the best constant hidden in O(k)?
Best lower bound is 2k-1 !
Can the polylog memory factors be improved?
Thank you !