Near-Entropy Hotlink Assignments

Consider a rooted tree

T

of arbitrary maximum degree

d

representing a collection of

n

web pages connected via a set of links, all reachable from a source home page represented by the root of

T

. Each web page

i

carries a weight

w

i

representative of the frequency with which it is visited. By adding hotlinks — shortcuts from a node to one of its descendents — we wish to minimize the expected number of steps

l

needed to visit pages from the home page, expressed as a function of the entropy

H

(

p

) of the access probabilities

p

. This paper introduces several new strategies for effectively assigning hotlinks in a tree. For assigning exactly one hotlink per node, our method guarantees an upper bound on

l

of 1.141

H

(

p

)+1 if

d

>2 and 1.08

H

(

p

)+ 2/3 if

d

=2. We also present the first efficient general methods for assigning at most

k

hotlinks per node in trees of arbitrary maximum degree, achieving bounds on

l

of at most

$\frac{2H(p)}{\log (k+1)}$

and

$\frac{H(p)}{\log (k+d) -- \log d}$

, respectively. Finally, we present an algorithm implementing these methods in

O

(

n

log

n

) time, an improvement over the previous

O

(

n

2

) time algorithms.