Detail

How a web scale Autosuggest system works

Autocomplete, or Autosuggest, is the feature that allows word/sentence/query completion to improve users efficiency/satisfaction.
Many modern software applications, e.g. web browsers, e-mail clients, cell phone sms clients, text/code editors and search engines have some form of Autosuggest.
In an open domain setting like a search engine, where the query can be virtually any string, suggesting relevant completions is far more difficult than, say, in a code editor, where the list of possible completions is well known and limited.
In this talk we describe the challenges of building a web-scale Autosuggest system for a major commercial search engine, Bing.
The range of challenges varies from relevance to engineering touching many areas of computer science, e.g. networks, systems architecture, algorithms and data structures, compilers, information retrieval, data mining, natural language processing, machine learning.
For relevance, Bing’s Autosuggest is available in 30+ countries, and the goal is always to present suggestions that are: clean (not promoting violence or illegal activity), correctly spelled, fresh and relevant to the user’s context. For engineering, the goal is to handle these large traffic loads (tens of thousands of keystrokes per second, 24/7) with low latency, gracefully supporting backend hardware/software issues (application/OS crashes, machines dying, a datacenter being disconnected…), using the available hardware resources as efficiently as possible.
Finally, to continuously improve the system, we discuss the importance of A/B tests, where small controlled changes are done to one element of the relevance or engineering stack (e.g. a new suggestion scoring model), and its impact is assessed by evaluating key metrics
automatically derived from the users interaction with the control and treatment systems (users randomly assigned to the control and treatment groups).