Section 14.6. Suggestion

14.6. Suggestion

Auto-Complete, Fill, Intelligent, Populate, Predict, Suggest, Wizard

Figure 14-18. Suggestion

14.6.1. Goal Story

Doc is typing out an electronic prescription. He intends to prescribe "Vancomycin 65 mg," but as soon as he types in "V", the system has already detected a handful of likely choices, based on the patient's history and Doc's prescription style. Doc selects "Vancomycin 65 mg" from the list and proceeds to the next field.

14.6.2. Problem

How can you improve throughput?

14.6.3. Forces

• Free text remains the most powerful way for humans to communicate with computers. The trend seems to be toward more typing than ever before due to instant messaging, blogging, and email. Even search engines are undergoing a transformation to become general-purpose, as described in Live Command-Line later in this chapter.

• When presented with a free text area, people don't always know what they're meant to type in.

• Though many users are now quick on the keyboard, there are still many users for whom the Web is a click-mostly experience.

• Typing speed remains a bottleneck even for fast typists, most of whom think faster than they can type.

• People make mistakes when they type.

14.6.4. Solution

Suggest words or phrases that are likely to complete what the user is typing. The user can then select the Suggestion and avoid typing it in full. The results usually come from an XMLHttpRequest Call (Chapter 6)the partial input is uploaded and the server responds with a collection of likely matches.

Suggestion has its roots in "combo boxes"fields on traditional GUI forms that combine a text input with a drop-down list. The elements are kept synchronized. The user is free to type any text, and the current selection in the list will track what's been typed so far. The user is also free to choose an element from the list, which will then be posted back to the text field. In some cases, the list constrains what the user types; in other cases, it's there to provide Suggestions only.

It's the latter style that has become popular in recent yearsfree text entry, with some Suggestions for completion at any time. Auto-completion became popular with Internet Explorer 5, which auto-completed fields based on user history. Most users are comfortable with the approach, as all the modern browsers offer a similar feature, and the technique is also popular in mobile phone text messaging and East Asian text entry.

In an Ajaxian context, Google set the standard with its introduction of Google Suggest (http://www.google.com/webhp?complete=1), which suggests the most popular terms to complete the user's search query. Its release surprised many, as Google had managed to completely replicate conventional combo-box behavior, but this time, the terms were dynamically fetched from the server instead of being present when the form was created.

The mechanics of a Suggestion usually work like this:

• A standard input field is used. At the same time, an initially invisible div element is created to contain the Suggestions as they appear. The input field needs an event handler to monitor the text it contains so as to ensure that the list always highlights whichever Suggestion matches.

• Instead of requesting a Suggestion upon each keypress, Submission Throttling is usually adopted. Thus, every 100 milliseconds or so, the browser checks whether anything has changed since the last request. If so, the server is passed the partial query as a GET-based XMLHttpRequest Call.

• The server then uses some algorithm to produce an ordered list of Suggestions.

• Back in the browser, the callback function picks up the Suggestions and does some Display Morphing (Chapter 5) to show them to the user in a format that allows them to be selected. Each entry will have an event handler, so that if the entry is clicked, the input field will be altered.

A combo-box is not the only way to render results, but it has the dual virtues of efficiency and familiarity. "Code Example: Kayak," later in this section, covers Kayak's implementation.

You might think the main benefit of a Suggestion is to cut down on typing, but that's not the case. If anything, it's often slower to enter a single word using Suggestion, as it's a distraction and probably requires some mousing. The main benefit is to offer a constrained set of choiceswhen there are more choices than would fit in a standard option list, but still a fixed set. For Google Suggest, it's a list of choices that are considered probable based on search history. In tagging web sites, it's a list of tag names that have been used in the past. In travel web sites, it's a list of airports you can include on your ticket.

14.6.5. Decisions

14.6.5.1. What algorithm will be used to produce the Suggestions?

Ultimately, the Suggestion algorithm needs to find the most likely completions.

A few rules of thumb:

• In general, historical data is the best predictor. Log what users commonly search for and use that as a basis for Suggestions. So when the user types "A," suggest the most frequent responses beginning with "A."

• Personalize. Instead of completing "A" with the most common "A"-query all users have entered, return the most common "A"-queries for this user. The only problem here is lack of data, so consider a collaborative filtering algorithm to provide Suggestions based on similar users.

• Recent history is a more pertinent guide, whether you're personalizing the results or not. In some cases, it makes sense to provide only recent queries. In other cases, consider weighting recent results more heavily, but taking into account older queries as well.

• In some cases, it might make more sense for the browser to provide Guesstimates (Chapter 13) rather than real results from the server in real-time. This information might be based on what's in a Browser-Side Cache (Chapter 13) and, potentially, on a few algorithms to help the browser decide what's relevant.

14.6.5.2. How will the Suggestions be ordered?

Typical ordering algorithms include:

• Estimated likelihood, e.g., historical frequency.

• How recently the query was last used.

• Alphabetical or numerical order.

• Application-specific ordering. A currency list often begins with the U.S. Dollar, for instance.

However you order your Suggestions, the first item is particularly important because it can be designed to enable the user to select the first element without explicitly choosing it from the list. For example, Google's combo-box implementation automatically inserts the first element in the text field, though with a text selection over the completion text so the user can easily override it.

14.6.5.3. How many Suggestions will be shown?

Deciding how many Suggestions to show is a balancing act. You want to show enough Suggestions to be useful, but not so many that the good ones get lost in the crowd. Space is limited as well, even if you use a pop-up list.

It's generally useful if your Suggestion algorithm not only ranks Suggestions, but also makes a relevance estimate. Then, you can ensure Suggestions are shown only if they are particularly useful. Sometimes it isn't really worth it to show any Suggestions.

14.6.5.4. What auxiliary information will be present with each Suggestion?

The core part of the Suggestion is always a word or phrase that completes what the user is typing. You can augment each Suggestion with supportive information. Google Suggest, for example, shows how many results each completion has. It would even be possible to present the Suggestions in a table, with several columns of background information per completion. Taken to an extreme, the Suggestion resembles a Live Search (see later in this chapter).

14.6.6. Real-World Examples

14.6.6.1. Kayak

Kayak (http://kayak.com) is a travel search engine that suggests airports as you type in a location (Figure 14-19). The Suggestions appear in a combo-box format similar to Google Suggest.

Figure 14-19. Kayak airport Suggestions

14.6.6.2. Google Suggest

Google Suggest (http://www.google.com/webhp?complete=1) was probably the first public usage of Suggestion and remains an excellent example. Results are shown in a combo-box style. The combo-box appearance is achieved with a custom control. A div is placed just under the text input, with a Suggestion on each row, and the zIndex property is used to make the div appear "in front of" the usual page content.

14.6.6.3. Delicious, Amazon

Delicious (http://del.icio.us) and Amazon (http://amazon.com) both offer Suggestions to help complete tags (Figure 14-20). As you type a tag, several Suggestions appear immediately and are populated below the field. You can click on a Suggestion to complete the term.

Figure 14-20. Amazon tag Suggestions

14.6.7. Code Example: Kayak

Kayak (http://kayak.com) is a slick, Ajaxian interface with a handy Suggestion feature for source and destination airports. The list of Suggestions appears below the input field, is referred to in the code as a smartBox, and exists as long as the input field has focus.

Whenever a key is pressed, the smartBox is abortedwhich stops any pending requestand a new request is initiated. A check is made to ensure that the text entry actually contains something, otherwise the smartBox is closed:

   function _typer(input)     {         if ((_input != null ) && _input.value.length > 0) {abortSmartBox( );_runSearch(input); }         else {_setValue(-1);closeSmartBox( );}     } 

_runSearch( ) kicks off a call to the server to receive the Suggestion list. The query goes to http://www.kayak.com/m/smarty.jsp?where=LOCATION. The result is some XML containing the airport names and codes and what appears to be an ID number, for example:

   <i>28501</i><m>L</m><d>London, United Kingdom</d> <a>LON</a> 

The callback function accumulates an HTML string to be inserted into the smartbox. A loop runs over each result, appending a div element to the HTML:

   var html = ""; var list = "";   for (var j = 0; j < ii.length; j++) {       var id=client.getTagText(results[0], "i", j);       var str=client.getTagText(results[0], "d", j);       var match=client.getTagText(results[0], "m", j);       ...       list += _divB + _spanB + icon + str + _spanE + _divE;cnt++;   } 

Also of interest is the optional icon, which appears beside the airport name, as shown in the preceding code. Depending on the resulting XML, the icon is chosen from one of two images:

   var _iconAir = "<img style='vertical-align: middle' src='/books/2/755/1/html/2//images/airport_icon.gif' border= '0'>";   var _iconLoc = "<img style='vertical-align: middle; visibility: hidden' src= '/images/place_icon.gif' border='0'>";   ...   icon = (match == "L") ? _iconLoc : _iconAir; 

An event handler monitors key presses. As the user moves up and down, the airport text is changed according to the selection, and the selection is incremented or decremented:

   case UP:       _cursel--;if (_cursel<0){_cursel=0;}selChoice(_cursel);   ...   case DOWN:       _cursel++;if (_cursel>=_ids.length){_cursel=_ids.length-1;}selChoice(_cursel); 

Finally, the value is set when the user clicks tab or enter. In the former case, focus will also proceed to the next field:

   case ENTER:       if (_ids.length>0){           _setValue(_cursel);           closeSmartBox( );       }   ...   case TAB:       if (_cursel>=0&&_cursel<_ids.length){_setValue(_cursel);} 

14.6.8. Alternatives

14.6.8.1. Selector

In some cases, a plain old HTML selection input will suffice. Most modern browsers support navigation through the drop-down with a keyboard, so it's an easy, viable alternative if the range of inputs is constrained.

14.6.9. Related Patterns

14.6.9.1. Browser-Side Cache

A Browser-Side Cache (Chapter 13) is a practical way to speed up the search.

14.6.9.2. Guesstimate

Sometimes the browser may be smart enough to derive Suggestions without resorting to the server. This is an application of Guesstimate (Chapter 13).

14.6.9.3. Predictive Fetch

Suggestion is similar to Predictive Fetch (Chapter 13). Predictive Fetch queries the server in anticipation of a future user action, whereas Suggestion queries the server to help the user complete the current action. In theory, you could actually combine the two patternsperform a Predictive Fetch to pull down some Suggestions that might be needed in the future. On an intranet, for instance, it might be practical to continuously make 26 parallel queries in anticipation of the user, who might type any letter of the alphabet.

14.6.9.4. Submission Throttling

To cut down on queries, don't issue an XMLHttpRequest Call upon every keypress. Instead, apply Submission Throttling (Chapter 10) to cap calls to a maximum frequency.

14.6.9.5. Highlight

When one of the Suggestions in the list matches the free text input, it's usually a good idea to Highlight (Chapter 16) it.

14.6.9.6. Lazy Registration

Lazy Registration (Chapter 17) involves the accumulation of profile information, and profiles can be used to generate personalized Suggestions. You can also retain user preferences regarding the appearance and timing of Suggestion lists.

14.6.9.7. Live Search

When full result details are provided, Suggestion resembles a Live Search (see the next pattern). However, the design goals are different and this should usually be reflected in the user interface. A Suggestion is intended to complete a word or phrase; a Live Search is intended to locate or report on an item being searched.

14.6.10. Want to Know More?

• "How Search Engines Rank Web Pages" by Danny Sullivan (http://searchenginewatch.com/webmasters/article.php/2167961)

• "Google Suggest Dissected" by Chris Justus (http://serversideguy.blogspot.com/2004/12/google-suggest-dissected.html)

14.6.11. Acknowledgments

Chris Justus's thorough analysis of Google Suggest (http://serversideguy.blogspot.com/2004/12/google-suggest-dissected.html) was very helpful in explaining the magic behind Google's Suggestion implementation.