{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:40:18Z","timestamp":1750308018493,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,10,1]],"date-time":"2007-10-01T00:00:00Z","timestamp":1191196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2007,10]]},"abstract":"<jats:p>\n            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\n            <jats:italic>hotlink enhancement<\/jats:italic>\n            problem involves finding a set of hotlinks minimizing this cost.\n          <\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/1281485.1281491","type":"journal-article","created":{"date-parts":[[2007,10,12]],"date-time":"2007-10-12T15:47:29Z","timestamp":1192204049000},"page":"20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Reducing human interactions in Web directory searches"],"prefix":"10.1145","volume":"25","author":[{"given":"Ori","family":"Gerstel","sequence":"first","affiliation":[{"name":"Cisco, San Jose, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Kutten","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eduardo Sany","family":"Laber","sequence":"additional","affiliation":[{"name":"PUC-Rio, Rio de Janeiro, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rachel","family":"Matichin","sequence":"additional","affiliation":[{"name":"The Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[{"name":"The Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Artur Alves","family":"Pessoa","sequence":"additional","affiliation":[{"name":"UFF, Niteri\u2014RJ, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Criston","family":"Souza","sequence":"additional","affiliation":[{"name":"PUC-Rio, Rio de Janeiro, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,10]]},"reference":[{"volume-title":"Working Notes of the AAAI Spring Symposium: Information Gathering from Heterogeneous, Distributed Environments","author":"Armstrong R.","key":"e_1_2_1_1_1","unstructured":"Armstrong , R. , Freitag , D. , Joachims , T. , and Mitchell , T . 1995. WebWatcher: A learning apprentice for the World Wide Web . In Working Notes of the AAAI Spring Symposium: Information Gathering from Heterogeneous, Distributed Environments . Stanford, CA, AAAI Press, 6--12. Armstrong, R., Freitag, D., Joachims, T., and Mitchell, T. 1995. WebWatcher: A learning apprentice for the World Wide Web. In Working Notes of the AAAI Spring Symposium: Information Gathering from Heterogeneous, Distributed Environments. Stanford, CA, AAAI Press, 6--12."},{"key":"e_1_2_1_2_1","first-page":"719","article-title":"Categorization by context","volume":"4","author":"Attardi","year":"1998","unstructured":"Attardi , di Marco, S., and Salvi , D. 1998 . Categorization by context . J. Universal Comput. Sci. 4 , 9, 719 -- 736 . Attardi, di Marco, S., and Salvi, D. 1998. Categorization by context. J. Universal Comput. Sci. 4, 9, 719--736.","journal-title":"J. Universal Comput. Sci."},{"volume-title":"Proceedings of the 9th Colloquium on Structural Information and Communication Complexity. 33--39","author":"Bose P.","key":"e_1_2_1_3_1","unstructured":"Bose , P. , Krizanc , D. , Langerman , S. , and Morin , P . 2002. Asymmetric communication protocols via hotlink assignments . In Proceedings of the 9th Colloquium on Structural Information and Communication Complexity. 33--39 . Bose, P., Krizanc, D., Langerman, S., and Morin, P. 2002. Asymmetric communication protocols via hotlink assignments. In Proceedings of the 9th Colloquium on Structural Information and Communication Complexity. 33--39."},{"volume-title":"Proceedings of the 11th International Symposium on Algorithms and Computation (ISAAC). 23--34","author":"Bose P.","key":"e_1_2_1_4_1","unstructured":"Bose , P. , Czyzowicz , J. , Gasieniec , L. , Kranakis , E. , Krizanc , D. , Pelc , A. , and Martin , M. V . 2000. Strategies for hotlink assignments . In Proceedings of the 11th International Symposium on Algorithms and Computation (ISAAC). 23--34 . Bose, P., Czyzowicz, J., Gasieniec, L., Kranakis, E., Krizanc, D., Pelc, A., and Martin, M. V. 2000. Strategies for hotlink assignments. In Proceedings of the 11th International Symposium on Algorithms and Computation (ISAAC). 23--34."},{"key":"e_1_2_1_5_1","first-page":"93","article-title":"Enhancing hyperlink structure for improving web performance","volume":"1","author":"Cyzyowicz J.","year":"2003","unstructured":"Cyzyowicz , J. , Kranakis , E. , Krizanc , D. , Pelc , A. , and Vargas Martin , M. 2003 . Enhancing hyperlink structure for improving web performance . J. Web Eng. 1 , 2, 93 -- 127 . Cyzyowicz, J., Kranakis, E., Krizanc, D., Pelc, A., and Vargas Martin, M. 2003. Enhancing hyperlink structure for improving web performance. J. Web Eng. 1, 2, 93--127.","journal-title":"J. Web Eng."},{"key":"e_1_2_1_6_1","unstructured":"Dmoz. 2007. DMOZ website. www.dmoz.org.  Dmoz. 2007. DMOZ website. www.dmoz.org."},{"key":"e_1_2_1_7_1","volume-title":"Web: Empirical Studies","author":"Fink J.","year":"1996","unstructured":"Fink , J. , Kobasa , A. , and Nill , A . 1996 . User-oriented adaptivity and adaptability in the AVANTI project. In Designing for the Web: Empirical Studies . Microsoft Usability Group , Redmond, WA . Fink, J., Kobasa, A., and Nill, A. 1996. User-oriented adaptivity and adaptability in the AVANTI project. In Designing for the Web: Empirical Studies. Microsoft Usability Group, Redmond, WA."},{"volume-title":"Proceedings of the International Symposium on Algorithms and Computation (ISAAC). 68--77","author":"Gerstel O.","key":"e_1_2_1_8_1","unstructured":"Gerstel , O. , Kutten , S. , Matichin , R. , and Peleg , D . 2003. Hotlink enhancement algorithms for web directories . In Proceedings of the International Symposium on Algorithms and Computation (ISAAC). 68--77 . Gerstel, O., Kutten, S., Matichin, R., and Peleg, D. 2003. Hotlink enhancement algorithms for web directories. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC). 68--77."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/197754.195680"},{"key":"e_1_2_1_10_1","unstructured":"Google. 2007. Google website. http:\/\/www.google.com\/.  Google. 2007. Google website. http:\/\/www.google.com\/."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.012"},{"volume-title":"Proceedings of the 8th Workshop on Algorithms and Data Structures","author":"Matichin R.","key":"e_1_2_1_12_1","unstructured":"Matichin , R. and Peleg , D . 2003. Approximation algorithm for hotlink assignments in web directories . In Proceedings of the 8th Workshop on Algorithms and Data Structures . Ottawa, Canada, 271--280. Matichin, R. and Peleg, D. 2003. Approximation algorithm for hotlink assignments in web directories. In Proceedings of the 8th Workshop on Algorithms and Data Structures. Ottawa, Canada, 271--280."},{"volume-title":"Proceedings of the 8th World Wide Web Conference.","author":"Perkowitz M.","key":"e_1_2_1_13_1","unstructured":"Perkowitz , M. and Etzioni , O . 1999. Towards adaptive web sites: Conceptual framework and case study . In Proceedings of the 8th World Wide Web Conference. Perkowitz, M. and Etzioni, O. 1999. Towards adaptive web sites: Conceptual framework and case study. In Proceedings of the 8th World Wide Web Conference."},{"volume-title":"Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX).","author":"Pessoa A.","key":"e_1_2_1_14_1","unstructured":"Pessoa , A. , Laber , E. , and Souza , C . 2004a. Efficient implementation of a hotlink assignment algorithm for web sites . In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). Pessoa, A., Laber, E., and Souza, C. 2004a. Efficient implementation of a hotlink assignment algorithm for web sites. In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX)."},{"volume-title":"Proceedings of the International Symposium on Algorithms and Computation (ISAAC).","author":"Pessoa A.","key":"e_1_2_1_15_1","unstructured":"Pessoa , A. , Laber , E. , and Souza , C . 2004b. Efficient algorithms for the hotlink assignment problem: The worst case search . In Proceedings of the International Symposium on Algorithms and Computation (ISAAC). Pessoa, A., Laber, E., and Souza, C. 2004b. Efficient algorithms for the hotlink assignment problem: The worst case search. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC)."},{"key":"e_1_2_1_16_1","unstructured":"Yahoo. 2007. Yahoo website. http:\/\/www.yahoo.com\/.  Yahoo. 2007. Yahoo website. http:\/\/www.yahoo.com\/."}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1281485.1281491","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1281485.1281491","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:13:46Z","timestamp":1750259626000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1281485.1281491"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,10]]}},"alternative-id":["10.1145\/1281485.1281491"],"URL":"https:\/\/doi.org\/10.1145\/1281485.1281491","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"type":"print","value":"1046-8188"},{"type":"electronic","value":"1558-2868"}],"subject":[],"published":{"date-parts":[[2007,10]]},"assertion":[{"value":"2007-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}