skip to main content
10.1145/1526709.1526762acmconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
research-article

Quicklink selection for navigational query results

Published: 20 April 2009 Publication History

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]
M. Bilenko and R. W. White. Mining the search trails of surfing crowds: Identifying relevant websites from user activity. In WWW, pages 51--60, 2008.
[2]
M. Bilenko, R. W. White, M. Richardson, and G. C. Murray. Talking the talk vs. walking the walk: Salience of information needs in querying vs. browsing. In SIGIR, pages 705--706, 2008.
[3]
P. Bose, E. Kranakis, D. Krizanc, M. V. Martin, J. Czyzowicz, A. Pelc, and L. Gasieniec. Strategies for hotlink assignments. In Algorithms and Computation, pages 23--34, 2000.
[4]
A. G. Buchner, M. Baumgarten, S. S. Anand, M. D. Mulvenna, and J. G. Highes. User-driven navigation pattern discovery from internet data. In WebKDD Workshop, pages 74--91, 1999.
[5]
I. V. Cadez, D. Heckerman, C. Meek, P. Smyth, and S. White. Model-based clustering and visualization of navigation patterns on a web site. Data Mining and Knowledge Discovery, 7(4):399--424, 2003.
[6]
D. Chakrabarti, R. Kumar, and K. Punera. Generating succinct titles for web urls. In KDD, pages 79--87, 2008.
[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]
C. Doerr, D. von Dincklage, and A. Diwan. Simplifying web traversals by recognizing behavior patterns. In Hypertext and Hypermedia, pages 105--114, 2007.
[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]
B. Hay, G. Wets, and K. Vanhoof. Mining navigation patterns using a sequence alignment method. Knowl. Inf. Syst., 6(2):150--163, 2004.
[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]
E. Kranakis, D. Krizanc, and S. M. Shende. Approximate hotlink assignment. Information Processing Letters, 90(3):121--128, 2004.
[13]
Y. Liu, B. Gao, T.-Y. Liu, Y. Zhang, Z. Ma, S. He, and H. Li. Browserank: Letting web users vote for page importance. In SIGIR, pages 451--458, 2008.
[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]
M. Perkowitz and O. Etzioni. Towards adaptive web sites: Conceptual framework and case study. WWW8/Computer Networks, 31(11--16):1245--1258, 1999.
[18]
M. Perkowitz and O. Etzioni. Adaptive web sites. CACM, 43(8):152---158, 2000.
[19]
S. Sakai, M. Togasaki, and K. Yamazaki. A note on greedy algorithms for the maximum weighted independent set problem. Discrete Applied Math., 126(2-3):313--322, 2003.
[20]
R. Srikant and Y. Yang. Mining web logs to improve website organization. In WWW, pages 430--437, 2001.
[21]
V. Vazirani. Approximation Algorithms. Cambridge University Press, 2001.
[22]
R. W. White, M. Bilenko, and S. Cucerzan. Studying the use of popular destinations to enhance web search interaction. In SIGIR, pages 159--166, 2007.

Cited By

View all
  • (2023)The Evolution of Web Search User Interfaces - An Archaeological Analysis of Google Search Engine Result PagesProceedings of the 2023 Conference on Human Information Interaction and Retrieval10.1145/3576840.3578320(55-68)Online publication date: 19-Mar-2023
  • (2018)The Characteristics of Voice SearchACM Transactions on Information Systems10.1145/318216336:3(1-28)Online publication date: 13-Mar-2018
  • (2016)One Query, Many ClicksProceedings of the 25th ACM International on Conference on Information and Knowledge Management10.1145/2983323.2983856(1423-1432)Online publication date: 24-Oct-2016
  • Show More Cited By

Index Terms

  1. Quicklink selection for navigational query results

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      WWW '09: Proceedings of the 18th international conference on World wide web
      April 2009
      1280 pages
      ISBN:9781605584874
      DOI:10.1145/1526709

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 20 April 2009

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. navigational queries
      2. quicklinks
      3. toolbar data
      4. trails

      Qualifiers

      • Research-article

      Conference

      WWW '09
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)5
      • Downloads (Last 6 weeks)1
      Reflects downloads up to 14 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2023)The Evolution of Web Search User Interfaces - An Archaeological Analysis of Google Search Engine Result PagesProceedings of the 2023 Conference on Human Information Interaction and Retrieval10.1145/3576840.3578320(55-68)Online publication date: 19-Mar-2023
      • (2018)The Characteristics of Voice SearchACM Transactions on Information Systems10.1145/318216336:3(1-28)Online publication date: 13-Mar-2018
      • (2016)One Query, Many ClicksProceedings of the 25th ACM International on Conference on Information and Knowledge Management10.1145/2983323.2983856(1423-1432)Online publication date: 24-Oct-2016
      • (2014)Approximately optimal facet value selectionScience of Computer Programming10.1016/j.scico.2013.07.01994:P1(18-31)Online publication date: 15-Nov-2014
      • (2013)Mining Summaries of Propagations2013 IEEE 13th International Conference on Data Mining10.1109/ICDM.2013.163(498-507)Online publication date: Dec-2013
      • (2013)Network visualisation as a way to the web usage analysisAslib Proceedings10.1108/0001253131129717765:1(40-53)Online publication date: Jan-2013
      • (2012)Automatic Link Generation for Search Engine OptimizationInternational Journal of Information and Education Technology10.7763/IJIET.2012.V2.163(401-403)Online publication date: 2012
      • (2011)Pseudo test collections for learning web search ranking functionsProceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval10.1145/2009916.2010058(1073-1082)Online publication date: 24-Jul-2011
      • (2011)Generalized link suggestions via web site clusteringProceedings of the 20th international conference on World wide web10.1145/1963405.1963420(77-86)Online publication date: 28-Mar-2011
      • (2011)Two-stream indexing for spoken web searchProceedings of the 20th international conference companion on World wide web10.1145/1963192.1963364(503-512)Online publication date: 28-Mar-2011
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media