Dynamic Hotlinks

摘要

Consider a directed rooted tree T = (V, E) representing a collection V of n web pages connected via a set E 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 are interested in minimizing the expected number of steps needed to visit pages from the home page. We give the first linear time algorithm for assigning hotlinks so that the number of steps to accede to a page i from the root of the tree reaches the entropy bound, i.e. is at most O(log W/(w_i)) where W = Σ_(i∈T) w_i The best previously known algorithm for this task runs in time O(n~2). We also give the first efficient data structure for maintaining hotlinks when nodes are added, deleted or their weights modified, in amortized time O(log W/(w_i)) per update. The data structure can be made adaptative, i.e. reaches the entropy bound in the amortized sense without knowing the weights W_i in advance.