Autosuggest enables people to select a query from a pull-down menu of suggestions when they start typing a query. You often find the query you want in the menu and select it, saving you extra keystrokes while reducing a chance of misspelling. It is a feature that people may take for granted but upon examination it involves a tremendous amount of technical sophistication and computational horsepower. In this blog Antonio Gulli who is our development manager for Autosuggest discusses how we implement the feature focusing on a new Autosuggest advancement we recently shipped called “Ghosting” which further optimizes the user experience.
- Dr. Harry Shum, Corporate Vice President, Bing R&D
As we’ve all experienced, sometimes search can be a hit-or-miss experience. You enter a query, scan through the results and refine your search until you find what you’re looking for. Autosuggest attempts to accelerate the process by providing a list of suggestions as soon as you start typing. Let’s look at the following example:
In a previous post, we highlighted how Ghosting in Autosuggest lets you get more done in less time. In this follow up, we would like to shed some light on the algorithms used to complete your query once Bing has confidence in the intent of your search.
Let’s consider the above example where someone begins typing the query prefix {american}. In this case, the intent is not yet clear. You could be searching for American Express because you need a new credit card, American Idol because you’re a fan of the show or American Girl because you’re looking to buy your daughter a birthday present. At this point, you can either pick one of the provided suggestions or continue to type a different word not yet captured by our suggestions. In order to provide these suggestions our search algorithms analyze billions of search queries and optimize the list based on multiple objective factors including how often people have searched with the prefix {e.g. american}. Now, observe the evolution of the suggestions when someone adds an additional letter. Immediately, our algorithms update the list of suggestions offering a refined selection.
If you type one more letter and the query is {american ai} the dominant intent becomes clear. Instead of picking one selection from the list by either clicking on the mouse or by using the keyboard cursor arrows, our algorithms immediately complete the query prefix with the most likely result to complete that task, in this case {american airlines}. Given the ability of the algorithms to quickly adapt to fresh data, you may observe different Ghosting results when typing these queries.
At first glance, the gains might seem negligible. But for Bing, where we consider speed and relevance to be paramount the gains are significant. Indeed, Ghosting increases the searching speed by 16% by reducing clicks and letters typed.
How do our algorithms identify the dominant intent? The key insight centers around previous queries that can be grouped into multiple topics with each topic representing a different search need. This algorithmic grouping occurs in the space of milliseconds between keystrokes.
Let’s look at another example where our algorithmic grouping can identify {lindsay lohan} as a truly dominant search intent for all the query prefixes beginning with {linds}. In this case, Bing takes into account all the past searches related to the name {lindsay lohan} which are more frequent than searches related to {lindsey vonn}. In this way, we speed up the search experience by completing the query and eliminating the need for you to use the mouse or keyboard cursor arrows.
How quickly are we able to predict truly dominant intent? Our algorithms are fueled by the millions of people who use our service every day so if you just type {f}, we know the majority of people on Bing are trying to get to Facebook so we “Ghost” the rest of the word. No surprise there.
Now let’s take a look behind the scenes at how we make all of this happen.
At Bing, we maintain a data structure commonly named in computer science as trie, which stores the millions of searches entered every day. A trie (short for retrieval) is a specialized data structure where all descendants of a node have a common prefix of the query associated with that node, and the root of the tree is associated with an empty symbol. Make sense?
Let’s illustrate with an example to clarify the definition. Below, you have a tree where the root node (top circle) is empty and you see edges departing from the root node. Each edge is labelled with a letter of the alphabet (for the sake of simplicity only the initial tree letters are represented). The root node represents the first letter that you are typing in the search box. In the case of “amex” that of course would be “a.” So we start with the letter “a” and continue as the letter “m” and then to the letter “e” and the letter “x” are typed. While this is happening we are looking at all of the myriad combinations of “ame” and trying to discern the most likely combination of letters to follow. Using this method, we are able to access the word “amex” previously stored in the trie. This time, let’s walk down the path of “ame” again but this time let’s follow the letter “r” and then “i”, “c”, “a” to access the word “america”.
Why do we take this approach? Well, the word “amex” and the word “america” share the prefix “ame” which is stored only once in our data structure. With this approach, we have an efficient way to assess the intent of your search based on the similarities of words. Keep in mind, that we perform this every time you type a letter. Storing common prefixes only once allows us to be very fast in retrieving the suggestions. Why is efficiency so important? We need to be efficient so we can quickly process several billion searches in the time it takes you to type another letter. Every millisecond counts.
That’s not all. In addition to processing suggestions, we are also running parallel algorithms that filter spam, detect adult or offensive content, check for spelling errors and classify the type of search you are attempting across categories.
Currently, we have a platform with multiple data layers. If a query suddenly becomes popular it will be inserted in our trie data structure within 5-15 minutes. Similarly, a query may already be in our trie but its dominance may change. For example, Lindsey Vonn has been in the news recently, and once we identify her as freshly topical, {lindsay lohan} may no longer be the dominant intent for {linds} as we outlined above.
Finally, ranking is also a critical component of Autosuggest. As soon as you begin to type we need to provide relevant suggestions. In a few milliseconds we evaluate how fresh the suggestions are, how many users have submitted them, how many times the suggestions have been selected in the past alongside over several hundred additional ranking signals.
We’re constantly looking for ways to make search faster and more relevant at Bing. Hopefully you found this interesting.
- Dr. Antonio Gulli, Principal Development Manager, Bing R&D
DIGITAL JUICE
No comments:
Post a Comment
Thank's!