A Taxonomy of Query Auto Completion Modes
Unni Krishnan, Alistair Moffat, Justin Zobel · 2017
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.