TY - JOUR
T1 - Approximate hotlink assignment
AU - Kranakis, Evangelos
AU - Krizanc, Danny
AU - Shende, Sunil
N1 - Funding Information:
1 Research supported in part by NSERC (Natural Sciences and Engineering Research Council) of Canada and MITACS (Mathematics of Information Technology and Complex Systems) grants.
PY - 2004/5/16
Y1 - 2004/5/16
N2 - Consider a directed rooted tree T=(V,E) of maximal degree d representing a collection V of web pages connected via a set E of links all reachable from a source home page, represented by the root of T. Each leaf web page carries a weight 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 the leaf pages from the home page. We give an O(N2) time algorithm for assigning hotlinks so that the expected number of steps to reach the leaves from the root of the tree is at most H(p)/(log(d+1)-(d/(d+1))logd)+(d+1)/d, where H(p) is the entropy of the probability (frequency) distribution p=〈p1,p 2,⋯,pN〉 on the N leaves of the given tree, i.e., pi is the weight on the ith leaf. The best known lower bound for this problem is H(p)/log(d+1). We also show how to adapt our algorithm to complete trees of a given degree d and in this case we prove it is optimal, asymptotically in d.
AB - Consider a directed rooted tree T=(V,E) of maximal degree d representing a collection V of web pages connected via a set E of links all reachable from a source home page, represented by the root of T. Each leaf web page carries a weight 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 the leaf pages from the home page. We give an O(N2) time algorithm for assigning hotlinks so that the expected number of steps to reach the leaves from the root of the tree is at most H(p)/(log(d+1)-(d/(d+1))logd)+(d+1)/d, where H(p) is the entropy of the probability (frequency) distribution p=〈p1,p 2,⋯,pN〉 on the N leaves of the given tree, i.e., pi is the weight on the ith leaf. The best known lower bound for this problem is H(p)/log(d+1). We also show how to adapt our algorithm to complete trees of a given degree d and in this case we prove it is optimal, asymptotically in d.
KW - Algorithms
KW - Hotlink
KW - Probability distribution
KW - Tree
KW - Web
UR - http://www.scopus.com/inward/record.url?scp=1842610616&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=1842610616&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2004.01.012
DO - 10.1016/j.ipl.2004.01.012
M3 - Article
AN - SCOPUS:1842610616
SN - 0020-0190
VL - 90
SP - 121
EP - 128
JO - Information Processing Letters
JF - Information Processing Letters
IS - 3
ER -