Designing phrase builder: a mobile real-time query expansion interface

ABSTRACT

As users enter web queries, real-time query expansion (RTQE) interfaces offer suggestions based on an index garnered from query logs. In selecting a suggestion, users can potentially reduce keystrokes, which can be very beneficial on mobile devices with deficient input means. Unfortunately, RTQE interfaces typically provide little assistance when only parts of an intended query appear among the suggestion choices. In this paper, we introduce Phrase Builder, an RTQE interface that reduces keystrokes by facilitating the selection of individual query words and by leveraging back-off query techniques to offer completions for out-of-index queries. We describe how we implemented a small memory footprint index and retrieval algorithm, and discuss lessons learned from three versions of the user interface, which was iteratively designed through user studies. Compared to standard auto-completion and typing, the last version of Phrase Builder reduced more keystrokes-per-character, was perceived to be faster, and was overall preferred by users.

REFERENCES

• 1: Beaulieu, M. 1997. Experiments with interfaces to support query expansion. Jour. of Documentation, 53(1), 8--19.
• 2: Beaulieu, M., Do. T., Payne, A., & Jones, S. 1997. ENQUIRE Okapi Project. British Library Research and Innovation Report 17.
• 3: Bentley, L. 1975. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509--517.
• 4: Church, K. & Smyth, B., 2007. Mobile content enrichment. Proc. of IUI, 112--121.
• 5: Church, K., Smyth, B., Cotter, P. & Bradley, K. 2007. Mobile information access: A study of emerging search behavior on the mobile Internet. ACM Transactions on the Web, 1(1), 1--38.
• 6: Church, K., Thiesson, B., & Ragno, R. 2007. K-best suffix arrays. Proc. of NAACL-HLT, companion volume, 17--20.
• 7: Church, K., Keane, M. T., & Smyth, B. 2005. Towards more intelligent mobile search. Proc. of IJCAI, 1675--1676.
• 8: Church, K. & Thiesson, B. 2005. The Wild Thing! Proc. of ACL, 93--96.
• 9: Croft, W. B. & Thompson, R. H. 1987. I3R: A new approach to the design of document retrieval systems. Jour. of the American Society for Information Science, 38(6), 389--404.
• 10: Cui, H., Wen, R. R., Nie, J. Y. & Ma, W. 2002. Probabilistic query expansion using query logs. Proc. of WWW, 325--332.
• 11: Efthimiadis, E. N. 1996. Query expansion. Annual Review of Information Systems and Technology, 31, 121--187.
• 12: Fowkes, H. & Beaulieu, M. 2000. Interactive searching behavior: Okapi experiment for TREC -8. Proc. of the IRSG 2000 Colloquium on IR Research.
• 13: http://www.google.com
• 14: http://www.piccolo2d.org
• 15: http://www.t9.com
• 16: http://www.yahoo.com
• 17: Ipsos Insight. 2006. Mobile phones could soon rival the PC as world's dominant Internet platform. http://www.ipsosna.com/news/pressrelease.cfm?id=3049, April 2006. Accessed June 2009.
• 18: Jelinek, F. 1997. Statistical methods for speech recognition. Cambridge, MA: MIT Press
• 19: Jones, M., Buchanan, G., & Thimbleby, H. 2002. Sorting out searching on small screen devices, Proc. of Mobile HCI, 81--94.
• 20: Kamvar, M. & Baluja, S. 2008. Query suggestions for mobile search: Understanding usage patterns. Proc. of CHI, 1013--1016.
• 21: Kamvar, M. & Baluja, S. 2006. A large scale study of wireless search behavior: Google mobile search. Proc. of CHI, 701--709.
• 22: Kamvar, M. & Baluja, S. 2006. The role of context in query input: Using contexual signals to complete queries on mobile devices. Proc. of Mobile HCI, 405--412.
• 23: Kang, T. 2008. Value share: global handset vendor financial metrics in Q1 2008. Strategy Analytics. Dated: 06-01-2008.
• 24: Katz, S. 1987. Estimation of probabilities from sparse data for the language model component of a speech recogniser. IEEE Transactions on Acoustics, Speech, and Signal Processing, 35(3), 400--401.
• 25: Koenenman, J. & Belkin, N. J. 1996. A case for inter-action: A study of interactive information retrieval behavior and effectiveness. Proc. of CHI, 205--212.
• 26: Lewis, C., & Rieman, J. 1993. Task-Centered User Interface Design: A Practical Introduction. Distributed via anonymous ftp (ftp.cs.colorado.edu).
• 27: MacKenzie, I., Kober, H., Smith, D., Jones, T. & Skepner, E. 2001 LetterWise: Prefix-based disambiguation for mobile text input. Proc. of UIST, 111--120.
• 28: MacKenzie, I., & Tanaka-Ishii, K. 2007. Text entry systems: Mobility, accessibility, universality. San Francisco: Morgan Kaufmann Publishers.
• 29: Manber, U. & Myers, G. 1990. Suffix arrays: A new method for on-line string searches, Proc. of SODA, 319--327.
• 30: Masui, T. 1999. POBox: An efficient text input method for handheld and ubiquitous computers. H. Gellersen, Ed. Lecture Notes in Computer Science, 1707, 288--300.
• 31: Paek, T., Thiesson, B., Ju, Y. C., & Lee, B. 2008. Search Vox: Leveraging multimodal refinement and partial knowledge for mobile voice search. Proc. of UIST, 141--150.
• 32: White, R. & Marchionini, G. 2007. Examining the effectiveness of real-time query expansion. Information Processing and Management, 43(3), 685--704.
• 33: Wigdor, D. & Balakrishnan, R. 2004. A comparison of consecutive and concurrent input text entry techniques for mobile phones. Proc. of CHI, 81--88.
• 34: Zhang, Z. & Nasraoui, O. 2006. Mining search engine query logs for query recommendations. Proc. of WWW, 1039--1040.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Design, Human Factors

Keywords:
auto-completion, interactive query expansion, mobile, real-time