Predicting query reformulation during web searching

ABSTRACT

his paper reports results from a study in which we automatically classified the query reformulation patterns for 964,780 Web searching sessions (composed of 1,523,072 queries) in order to predict what the next query reformulation would be. We employed an n-gram modeling approach to describe the probability of searchers transitioning from one query reformulation state to another and predict their next state. We developed first, second, third, and fourth order models and evaluated each model for accuracy of prediction. Findings show that Reformulation and Assistance account for approximately 45 percent of all query reformulations. Searchers seem to seek system searching assistant early in the session or after a content change. The results of our evaluations show that the first and second order models provided the best predictability, between 28 and 40 percent overall, and higher than 70 percent for some patterns. Implications are that the n-gram approach can be used for improving searching systems and searching assistance in real time.

REFERENCES

• 1: Piotr D. Adamczyk , Brian P. Bailey, If not now, when?: the effects of interruption at different moments within task execution, Proceedings of the SIGCHI conference on Human factors in computing systems, p.271-278, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985727]
• 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: N. J. Belkin , D. Kelly , G. Kim , J.-Y. Kim , H.-J. Lee , G. Muresan , M.-C. Tang , X.-J. Yuan , C. Cool, Query length in interactive information retrieval, 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.860474]
• 4: Belkin, N., Oddy, R. and Brooks, H. Ask for information retrieval, parts 1 & 2. Journal of Documentation, 38, 2 1982), 61--71, 145--164.
• 5: 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]
• 6: Bernard J. Jansen , Udo Pooch, A review of web searching studies and a framework for future research, Journal of the American Society for Information Science and Technology, v.52 n.3, p.235-246, Feb. 1, 2001 [doi>10.1002/1097-4571(2000)9999:9999<::AID-ASI1607>3.3.CO;2-6]
• 7: Meadow, C. T., Hewett, T. T. and Aversa, E. A computer intermediary for interactive database searching ii: Evaluation. Journal of the American Society for Information Science, 331982), 357--364.
• 8: Park, S., Bae, H. and Lee, J. End user searching: A Web log analysis of NAVER, a Korean Web search engine. Library & Information Science Research, 27, 2 2005), 203--221.
• 9: Soo Young Rieh , Hong Xie, Analysis of multiple query reformulations on the web: the interactive information retrieval context, Information Processing and Management: an International Journal, v.42 n.3, p.751-768, May 2006 [doi>10.1016/j.ipm.2005.05.005]
• 10: Zhong Su , Qiang Yang , Hong-Jiang Zhang, A prediction system for multimedia pre-fetching in Internet, Proceedings of the eighth ACM international conference on Multimedia, p.3-11, October 2000, Marina del Rey, California, United States [doi>10.1145/354384.354394]
• 11: Peiling Wang , Michael W. Berry , Yiheng Yang, Mining longitudinal web queries: trends and patterns, Journal of the American Society for Information Science and Technology, v.54 n.8, p.743-758, June 2003 [doi>10.1002/asi.10262]

INDEX TERMS

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

General Terms:
Human Factors

Keywords:
n-grams, query reformulation, stochastic process, web queries, web sessions