Studying trailfinding algorithms for enhanced web search

ABSTRACT

Search engines return ranked lists of Web pages in response to queries. These pages are starting points for post-query navigation, but may be insufficient for search tasks involving multiple steps. Search trails mined from toolbar logs start with a query and contain pages visited by one user during post-query navigation. Implicit endorsements from many trails can enhance result ranking. Rather than using trails solely to improve ranking, it may also be worth providing trail information directly to users. In this paper, we quantify the benefit that users currently obtain from trail-following and compare different methods for finding the best trail for a given query and each top-ranked result. We compare the relevance, topic coverage, topic diversity, and utility of trails selected using different methods, and break out findings by factors such as query type and origin relevance. Our findings demonstrate value in trails, highlight interesting differences in the performance of trailfinding algorithms, and show we can find best-trails for a query that outperform the trails most users follow. Findings have implications for enhancing Web information seeking using trails.

References

1. Agichtein, E., Brill, E. & Dumais, S. (2006). Improving web search ranking by incorporating user behavior information. Proc. SIGIR, 19--26.
2. Bates, M.J. (1989). The design of browsing and berrypicking techniques for the online search interface. Online Review, 13(5): 407--424.
3. Bilenko, M. & White, R.W. (2008). Mining the search trails of surfing crowds: identifying relevant websites from user activity. Proc. WWW, 51--60.
4. Bush, V. (1945). As we may think. Atl. Monthly, 3(2): 37--46.
5. Chalmers, M., Rodden, K. & Brodbeck, D. (1998). The order of things: activity-centered information access. Proc. WWW.
6. Clarke, C.L.A. et al. (2008). Novelty and diversity in information retrieval evaluation. Proc. SIGIR, 659--666.
7. Cole, M. et al. (2009). Usefulness as the criterion for evaluation of interactive information retrieval. Proc. HCIR, 1--4.
8. Downey, D., Dumais, S. & Horvitz, E. (2007). Models of searching and browsing: languages, studies, and application. Proc. IJCAI, 2740--2747.
9. Fox, S. et al. (2005). Evaluating implicit measures to improve the search experience. TOIS, 23(2): 147--168.
10. Freyne, J. et al. (2007). Collecting community wisdom: integrating social search and social navigation. IUI, 52--61.
11. Guinan, C. & Smeaton, A.F. (1993). Information retrieval from hypertext using dynamically planned guided tours. Proc. ECHT, 122--130.
12. Hammond, N. & Allison, L. (1988). Travels around a learning support environment: rambling, orienteering, or touring? Proc. SIGCHI, 269--273.
13. Joachims, T. (2002). Optimizing search engines using click-through data. Proc. SIGKDD, 133--142.
14. Joachims, T., Freitag, D. & Mitchell, T. (1997). WebWatcher: a tour guide for the world wide web. Proc. IJCAI, 770--775.
15. Olston, C. & Chi, E.H. (2003). ScentTrails: integrating browsing and searching on the web. TOCHI, 10(3): 1--21.
16. O'Day, V. & Jeffries, R. (1993). Orienteering in an information landscape: how information seekers get from here to there. Proc. INTERCHI, 438--445.
17. Pandit, S. & Olston, C. (2007). Navigation-aided retrieval. Proc. WWW, 391--400.
18. Pirolli, P. & Card, S.K. (1999). Information foraging. Psychological Review, 106(4): 643--675.
19. Shen, X., Dumais, S. & Horvitz, E. (2005). Analysis of topic dynamics in web search. Proc. WWW, 1102--1103.
20. Singhal, A. (2001). Modern information retrieval: a brief overview. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 24(4): 35--43.
21. Teevan, J. et al. (2004). The perfect search engine is not enough: a study of orienteering behavior in directed search. Proc. SIGCHI, 415--422.
22. Trigg, R.H. (1988). Guided tours and tabletops: tools for communicating in a hypertext environment. TOIS, 6(4).
23. Vakkari, P. & Taneli, M. (2009). Comparing google to ask-a-librarian service for answering factual and topic questions. Proc. EDCL, 352--363.
24. Wang, X. & Zhai, C. (2009). Beyond hyperlinks: organizing information footprints in search logs to support effective browsing. Proc. CIKM, 1237--1246.
25. Wexelblat, A. & Maes, P. (1999). Footprints: history-rich tools for information foraging. Proc. SIGCHI, 270--277.
26. Wheeldon, R. & Levene, M. (2003). The best trail algorithm for assisted navigation of web sites. Proc. LA-WEB, 166.
27. White, R.W., Bilenko, M., & Cucerzan, S. (2007). Studying the use of popular destinations to enhance web search interaction. Proc. SIGIR, 159--166.
28. White, R.W. & Drucker, S.M. (2007). Investigating behavioral variability in web search. Proc. WWW, 21--30.
29. White, R.W. & Huang, J. (2010). Assessing the scenic route: measuring the value of search trails in web logs. Proc. SIGIR
30. Zellweger, P.T. (1989). Scripted documents: a hypermedia path mechanism. Proc. Hypertext, 1--14.

Index Terms

• Information systems

  • Information retrieval

    • Information retrieval query processing

    • Retrieval models and ranking

    • Retrieval tasks and goals