Share icon Three circles with dashes Person icon Man with pen You Tube Logo Just "You tube" text Facebook logo Small letter f Search icon Magnifier Twitter logo Simplified small bird Email icon Envelope
Skip to main
Israel bds : Dialogue Through Science

Reducing human interactions in Web directory searches

Consider a website containing a collection of webpages with data such as in Yahoo or the Open Directory project

Israel bds : Dialogue Through Science

Authors: Ori Gerstel, Eduardo Sany Laber, Shay Kutten, Rachel Matichin, David Peleg, Artur Alves Pessoa, Criston Souza.

Consider a website containing a collection of webpages with data such as in Yahoo or the Open Directory project. Each page is associated with a weight representing the frequency with which that page is accessed by users. In the tree hierarchy representation, accessing each page requires the user to travel along the path leading to it from the root. By enhancing the index tree with additional edges (hotlinks) one may reduce the access cost of the system. In other words, the hotlinks reduce the expected number of steps needed to reach a leaf page from the tree root, assuming that the user knows which hotlinks to take. The hotlink enhancement problem involves finding a set of hotlinks minimizing this cost.

This article proposes the first exact algorithm for the hotlink enhancement problem. This algorithm runs in polynomial time for trees with logarithmic depth. Experiments conducted with real data show that significant improvement in the expected number of accesses per search can be achieved in websites using this algorithm. These experiments also suggest that the simple and much faster heuristic proposed previously by Czyzowicz et al. [2003] creates hotlinks that are nearly optimal in the time savings they provide to the user.

The version of the hotlink enhancement problem in which the weight distribution on the leaves is unknown is discussed as well. We present a polynomial-time algorithm that is optimal for any tree for any depth.

Full article


Israel BDS – building dialogue through science – aims to promote the kind of international collaboration that can lead to true understanding between people. Israel BDS stands for the free and open exchange of ideas among scientists everywhere. By reporting on the benefits of Israeli-international scientific research and the web of connections that these scientists create around the world, Israel BDS takes a vibrant approach to highlighting the global necessity of continued international scientific collaboration.