Quicklink selection for navigational query results

ABSTRACT

Quicklinks for a website are navigational shortcuts displayed below the website homepage on a search results page, and that let the users directly jump to selected points inside the website. Since the real-estate on a search results page is constrained and valuable, picking the best set of quicklinks to maximize the benefits for a majority of the users becomes an important problem for search engines. Using user browsing trails obtained from browser toolbars, and a simple probabilistic model, we formulate the quicklink selection problem as a combinatorial optimizaton problem. We first demonstrate the hardness of the objective, and then propose an algorithm that is provably within a factor of 1-1/e of the optimal. We also propose a different algorithm that works on trees and that can find the optimal solution; unlike the previous algorithm, this algorithm can incorporate natural constraints on the set of chosen quicklinks. The efficacy of our methods is demonstrated via empirical results on both a manually labeled set of websites and a set for which quicklink click-through rates for several webpages were obtained from a real-world search engine.

REFERENCES

• 1: Mikhail Bilenko , Ryen W. White, Mining the search trails of surfing crowds: identifying relevant websites from user activity, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367505]
• 2: Mikhail Bilenko , Ryen W. White , Matthew Richardson , G. Craig Murray, Talking the talk vs. walking the walk: salience of information needs in querying vs. browsing, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390461]
• 3: Prosenjit Bose , Evangelos Kranakis , Danny Krizanc , Miguel Vargas Martin , Jurek Czyzowicz , Andrzej Pelc , Leszek Gasieniec, Strategies for Hotlink Assignments, Proceedings of the 11th International Conference on Algorithms and Computation, p.23-34, December 18-20, 2000
• 4: Matthias Baumgarten , Alex G. Büchner , Sarabjot S. Anand , Maurice D. Mulvenna , John G. Hughes, User-Driven Navigation Pattern Discovery from Internet Data, Revised Papers from the International Workshop on Web Usage Analysis and User Profiling, p.74-91, August 15, 1999
• 5: Igor Cadez , David Heckerman , Christopher Meek , Padhraic Smyth , Steven White, Model-Based Clustering and Visualization of Navigation Patterns on a Web Site, Data Mining and Knowledge Discovery, v.7 n.4, p.399-424, October 2003 [doi>10.1023/A:1024992613384]
• 6: Deepayan Chakrabarti , Ravi Kumar , Kunal Punera, Generating succinct titles for web URLs, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401905]
• 7: J. Czyzowicz, E. Kranakis, D. Krizanc, A. Pelc, and M. M. Vargas. Enhancing hyperlink structure for improving web performance. J. Web Engineering, 1(2):93--127, 2003.
• 8: Christian Doerr , Daniel von Dincklage , Amer Diwan, Simplifying web traversals by recognizing behavior patterns, Proceedings of the eighteenth conference on Hypertext and hypermedia, September 10-12, 2007, Manchester, UK [doi>10.1145/1286240.1286268]
• 9: Y. Fu, K. Sandu, and M.-Y. Shih. Clustering of web users based on access patterns. In WebKDD Workshop, pages 21--38, 1999.
• 10: Birgit Hay , Geert Wets , Koen Vanhoof, Mining Navigation Patterns Using a Sequence Alignment Method, Knowledge and Information Systems, v.6 n.2, p.150-163, March 2004 [doi>10.1007/s10115-003-0109-6]
• 11: E. Kranakis, D. Krizanc, and M. V. Martin. Optimizing web server's data transfer with hotlinks. In IADIS Intl. Conf. on WWW/Internet, pages 341--346, 2003.
• 12: Evangelos Kranakis , Danny Krizanc , Sunil Shende, Approximate hotlink assignment, Information Processing Letters, v.90 n.3, p.121-128, 16 May 2004 [doi>10.1016/j.ipl.2004.01.012]
• 13: Yuting Liu , Bin Gao , Tie-Yan Liu , Ying Zhang , Zhiming Ma , Shuyuan He , Hang Li, BrowseRank: letting web users vote for page importance, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390412]
• 14: P. Mayr. Website entries from a web log file perspective -- a new log file measure. In Proceedings of the AoIR-ASIST Workshop on Web Science Research Methods, 2004.
• 15: G. L. Nemhauser and L. A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 3(3):177--188, 1978.
• 16: G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions. Mathematical Programming, 14:265--294, 1978.
• 17: Mike Perkowitz , Oren Etzioni, Towards adaptive Web sites: conceptual framework and case study, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1245-1258, May 17, 1999
• 18: Mike Perkowitz , Oren Etzioni, Adaptive Web sites, Communications of the ACM, v.43 n.8, p.152-158, Aug. 2000 [doi>10.1145/345124.345171]
• 19: Shuichi Sakai , Mitsunori Togasaki , Koichi Yamazaki, A note on greedy algorithms for the maximum weighted independent set problem, Discrete Applied Mathematics, v.126 n.2-3, p.313-322, 15 March 2003 [doi>10.1016/S0166-218X(02)00205-6]
• 20: Ramakrishnan Srikant , Yinghui Yang, Mining web logs to improve website organization, Proceedings of the 10th international conference on World Wide Web, p.430-437, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372097]
• 21: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 22: Ryen W. White , Mikhail Bilenko , Silviu Cucerzan, Studying the use of popular destinations to enhance web search interaction, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277771]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.m Miscellaneous

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
navigational queries, quicklinks, toolbar data, trails