Approximate hotlink assignment

Evangelos Kranakis, Danny Krizanc, Sunil Shende

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

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.

Original languageEnglish (US)
Pages (from-to)121-128
Number of pages8
JournalInformation Processing Letters
Volume90
Issue number3
DOIs
StatePublished - May 16 2004

Fingerprint

Websites
Leaves
Assignment
Roots
Rooted Trees
Asymptotically Optimal
Pi
Entropy
Lower bound
Vertex of a graph

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this

Kranakis, Evangelos ; Krizanc, Danny ; Shende, Sunil. / Approximate hotlink assignment. In: Information Processing Letters. 2004 ; Vol. 90, No. 3. pp. 121-128.
@article{37972d67f6a0438893fbeab1e6894b40,
title = "Approximate hotlink assignment",
abstract = "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.",
author = "Evangelos Kranakis and Danny Krizanc and Sunil Shende",
year = "2004",
month = "5",
day = "16",
doi = "10.1016/j.ipl.2004.01.012",
language = "English (US)",
volume = "90",
pages = "121--128",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "3",

}

Approximate hotlink assignment. / Kranakis, Evangelos; Krizanc, Danny; Shende, Sunil.

In: Information Processing Letters, Vol. 90, No. 3, 16.05.2004, p. 121-128.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Approximate hotlink assignment

AU - Kranakis, Evangelos

AU - Krizanc, Danny

AU - Shende, Sunil

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.

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

VL - 90

SP - 121

EP - 128

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 3

ER -