A Taxonomy of Query Auto-Completion Modes

Unni Krishnan
School of Computing and Information Systems, The University of Melbourne, Victoria 3010, Australia.

Alistair Moffat
School of Computing and Information Systems, The University of Melbourne, Victoria 3010, Australia.

Justin Zobel
School of Computing and Information Systems, The University of Melbourne, Victoria 3010, Australia.

Status

Proc. 22nd Australasian Document Computing Symp., Brisbane, Australia, December 2017, pages 6.1-6.8.

Abstract

Query auto completion mechanisms assist users to formulate search requests by suggesting possible queries corresponding to incomplete text they have typed. Keystroke by keystroke, these mechanisms proceed by finding matching strings from resources such as logs that have captured the behavior of previous users; they might also be informed by key phrases extracted from indexed documents, including, for example, anchor-text strings. Here we explore the range of ways, or modes, in which strings might be thought of as ``matching'' a partially typed query, and hence develop a taxonomy of possible approaches, each requiring different implementation structures and algorithms. Past work in the field has typically focused on only one or another of the modes, creating a lack of clarity as to exactly what challenge is being addressed. We use our taxonomy to survey options for auto completion and provide preliminary measurements in regard to their computational cost, using a range of public implementations.

Full text

https://doi.org/10.1145/3166072.3166081