Evaluation of natural user interfaces in query auto-completion

The Bing interface showing the search term 'who invented the' and a list of search suggestions below

Project overview

Query Auto-Completions (QAC) are the queries presented to users in the course of typing a query into a search box. At each additional key stroke, these QAC can change and update. In this project, the researchers are investigating the underlying mechanisms of QAC systems, their cost and their efficiency, with the aim of obtaining deeper insights into their design and performance characteristics.

Typing on a mobile phone is naturally slower and more difficult because latencies are higher and screens are smaller. The research team is seeking to understand if these differences change the way in which users interact with the QAC system and whether they rely more or less on QAC as they move across different hardware platforms.

The use of existing measures to evaluate Information Retrieval (IR) systems is inherently difficult, prompting the need to devise novel evaluation metrics to measure the performance of QAC systems. Through user studies, the research team seeks to understand how well different QAC systems satisfy users’ information needs and whether there are recognised differences in their use of QAC on different hardware platforms.

The goal of the project is to formalise the cost of building and maintaining a QAC system, to model novel QAC approaches with an emphasis on improving the NUI experience by understanding thevariations across multiple QAC scenarios, and to measure the performance of QAC systems acrossthese scenarios.


This project is a collaboration between Microsoft and the Microsoft Research Centre for Social Natural User Interfaces (SocialNUI) at the University of Melbourne.

Project team

  • Alistair Moffat, Professor, School of Computing and Information Systems, The University of Melbourne
  • Justin Zobel, Professor, School of Computing and Information Systems, The University of Melbourne
  • Peter Bailey, Principal Applied Scientist, Microsoft
  • David Hawking, Partner Architect, Microsoft
  • Bodo von Billerbeck, Senior Applied Scientist, Microsoft
  • Unnikrishnan Thoombayil Asokan, PhD Candidate, School of Computing and Information Systems, The University of Melbourne

Contact details


Krishnan, U. (2018) Design and Evaluation of Query Auto Completion Mechanisms. In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval (SIGIR '18). ACM, New York, NY, USA, 1463–1463. DOI: 10.1145/3209978.3210227

Krishnan, U., Moffat, A. & Zobel, J. (2017) A Taxonomy of Query Auto-Completion Modes. In Proceedings of the 22nd Australasian Document Computing Symposium, 7–8 December 2017, Brisbane, Australia. DOI: 10.1145/3166072.3166081