Beyond the session timeout: automatic hierarchical segmentation of search topics in query logs

ABSTRACT

Most analysis of web search relevance and performance takes a single query as the unit of search engine interaction. When studies attempt to group queries together by task or session, a timeout is typically used to identify the boundary. However, users query search engines in order to accomplish tasks at a variety of granularities, issuing multiple queries as they attempt to accomplish tasks. In this work we study real sessions manually labeled into hierarchical tasks, and show that timeouts, whatever their length, are of limited utility in identifying task boundaries, achieving a maximum precision of only 70%. We report on properties of this search task hierarchy, as seen in a random sample of user interactions from a major web search engine's log, annotated by human editors, learning that 17% of tasks are interleaved, and 20% are hierarchically organized. No previous work has analyzed or addressed automatic identification of interleaved and hierarchically organized search tasks. We propose and evaluate a method for the automated segmentation of users' query streams into hierarchical units. Our classifiers can improve on timeout segmentation, as well as other previously published approaches, bringing the accuracy up to 92% for identifying fine-grained task boundaries, and 89-97% for identifying pairs of queries from the same task when tasks are interleaved hierarchically. This is the first work to identify, measure and automatically segment sequences of user queries into their hierarchical structure. The ability to perform this kind of segmentation paves the way for evaluating search engines in terms of user task completion.

REFERENCES

• 1: Comscore announces new "visits" metric for measuring user engagement, 2007. http://www.comscore.com/press/release.asp?press=1246.
• 2: Peter Anick, Using terminological feedback for web search refinement: a log-based study, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860453]
• 3: Peter G. Anick , James Pustejovsky, Automatic construction of faceted terminological feedback for context-based information retrieval, Brandeis University, Waltham, MA, 1999
• 4: Lara D. Catledge , James E. Pitkow, Characterizing browsing strategies in the World-Wide Web, Proceedings of the Third International World-Wide Web conference on Technology, tools and applications, p.1065-1073, April 1995, Darmstadt, Germany
• 5: D. Downey, S. Dumais, and E. Horvitz. Models of searching and browsing: Languages, studies, and applications. Journal of the American Society for Information Science and Technology (JASIST), 58(6):862--871, 2007.
• 6: Daqing He , Ayse Göker , David J. Harper, Combining evidence for automatic web session identification, Information Processing and Management: an International Journal, v.38 n.5, p.727-742, September 2002 [doi>10.1016/S0306-4573(01)00060-7]
• 7: Scott B. Huffman , Michael Hochster, How well does result relevance predict session satisfaction?, 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.1277839]
• 8: B. J. Jansen, A. Spink, C. Blakely, and S. Koshman. Defining a session on web search engines. Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), 2000.
• 9: Tessa Lau , Eric Horvitz, Patterns of search: analyzing and modeling Web query refinement, Proceedings of the seventh international conference on User modeling, p.119-128, June 1999, Banff, Canada
• 10: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 11: Alan L. Montgomery , Christos Faloutsos, Identifying Web Browsing Trends and Patterns, Computer, v.34 n.7, p.94-95, July 2001 [doi>10.1109/2.933515]
• 12: H. Cenk Ozmutlu , Fatih Çavdur, Application of automatic topic identification on excite web search engine data logs, Information Processing and Management: an International Journal, v.41 n.5, p.1243-1262, September 2005 [doi>10.1016/j.ipm.2004.04.018]
• 13: H. C. Ozmutlu, F. Cavdur, A. Spink, and S. Ozmutlu. Investigating the performance of automatic new topic identification across multiple datasets. In Proceedings 69th Annual Meeting of the American Society for Information Science and Technology (ASIST) 43, Austin (US), 2006.
• 14: Seda Ozmutlu, Automatic new topic identification using multiple linear regression, Information Processing and Management: an International Journal, v.42 n.4, p.934-950, July 2006 [doi>10.1016/j.ipm.2005.10.002]
• 15: Filip Radlinski , Thorsten Joachims, Query chains: learning to rank from implicit feedback, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081899]
• 16: B. W. Silverman. Density Estimation. Chapman and Hall, London.
• 17: Craig Silverstein , Hannes Marais , Monika Henzinger , Michael Moricz, Analysis of a very large web search engine query log, ACM SIGIR Forum, v.33 n.1, p.6-12, Fall 1999 [doi>10.1145/331403.331405]
• 18: A. Spink, B. J. Jansen, and H. C. Ozmultu. Use of query reformulation and relevance feedback by Excite users. Internet Research: Electronic Networking Applications and Policy, 10(4):317--328, 2000.
• 19: Amanda Spink , Minsoo Park , Bernard J. Jansen , Jan Pedersen, Multitasking during web search sessions, Information Processing and Management: an International Journal, v.42 n.1, p.264-275, January 2006 [doi>10.1016/j.ipm.2004.10.004]
• 20: Jaime Teevan , Eytan Adar , Rosie Jones , Michael Potts, History repeats itself: repeat queries in Yahoo's logs, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148326]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
query log segmentation, query session, query session boundary detection, search goal