Paper Info
Title
An experimental study of recent hotlink assignment algorithms
Abstract
The concept of hotlink assignment aims at enhancing the structure of Web sites such that the user's expected navigation effort is minimized. We concentrate on sites that are representable by trees and assume that each leaf carries a weight representing its popularity. The problem of optimally adding at most one additional outgoing edge (“hotlink”) to each inner node has been widely studied. A considerable number of approximation algorithms have been proposed and worst-case bounds for the quality of the computed solutions have been given. However, only little is known about the practical behavior of most of these algorithms. This article contributes to closing this gap by evaluating all recently proposed strategies experimentally. Our experiments are based on trees extracted from real Web sites, as well as on synthetic instances. The latter are generated by a new method that simulates the growth of a Web site over time. Finally, we present a new heuristic that is easy to implement and exhibits excellent behavior in practice.
Year
DOI
Venue
2008
10.1145/1671970.1671971
Journal of Experimental Algorithmics (JEA)
Keywords
DocType
Volume
hotlink,real web site,excellent behavior,search tree,hotlink assignment,additional outgoing edge,experimental study,approximation algorithm,recent hotlink assignment algorithm,computed solution,new heuristic,approximation,practical behavior,new method,web site
Conference
15,
Citations 
PageRank 
References 
5
0.45
12
Authors
1
Name
Order
Citations
PageRank
Tobias Jacobs1544.32