GoogleSuggest

Introduction[]

Google Suggest is a service that provides real-time keyword suggestions as users type in the search box. On the server side, Google Suggest use a wide range of information retrieval algorithms to predict the queries users are most likely to want to see. For example, Google Suggest uses data about the overall popularity of various searches to help rank the refinements it offers. However, for the purpose of this project, we will focus on the client side technologies and show how Google Suggest implements its dynamic interface.

Analysis[]

We analyzed the techniques used in Google Suggest to send out real time request to server for keyword suggestion. Mainloop() is the function where requests to Google server are sent . This function after initial setup, calls itself in a loop. This loop is time driven rather than keystroke driven. This would handle fast typers on slow connections. For instance, if a user types 3 characters between timeouts, only a single request would go out to server. So, a timeout mechanism periodically checks if the state of the input field has changed. The value of timeout is also adjusted overtime. If the state of the input field has changed between two timeouts, the program first looks up the query in the cache it uses to store old results. If the result is present, no communication between server and browser is needed. Only if the input field has changed a call out is made (XMLHTTPRequest) to server. The code also handles older browsers which do not support XMLHTTPRequest object by using cookies and frame reloading. The caching technique also significantly reduces the latency when users backspace.

mainLoop=function()
  {

  //if there has been a change in input field between now and last timeout.
  
  if(oldInputFieldValue!=currentInputFieldValue){ 
    if(!da)
      {
      //convert query into a valid URI
      var Za=escapeURI(currentInputFieldValue);
      
      //looking in cache
      var ma=resultCache[currentInputFieldValue];  
      
      //Found in cache
      if(ma)                                              
        {
        Va=-1;
        
        //retrieval 
        sendRPCDone(B,currentInputFieldValue,ma[0],ma[1],B.completeDiv.prefixStrings)
      	}
      else
        {
	//timeout adjustment incremented
        timeoutAdjustment++;
       
        //new timestamp 
        Va=(new Date()).getTime();
        
        // if the browser supports XMLHTTPRequest
        if(hasXMLHTTP)
          {
          callGoogle(Za)
          }
        
        // if the browser does not support XMLHTTPRequest
        else
          {
          setCookie("qu",Za,null,_completeSearchString,null,null);
          frames["completionFrame"].document.location.reload(true)
          }
        }
      inputField.focus()
      }
    da=false
    }
  
  // oldFieldValue updated
  oldInputFieldValue=currentInputFieldValue;
  
  // time out set based on new timeoutAdjustment
  setTimeout("mainLoop()",recalculateTimeout(timeoutAdjustment));
  return true
}

If the query is not already present in the cache, the program will send an XMLHTTPRequest to the Google server and get back an XML file containing a list of suggestions. An example of the returned XML file is given in the FAQ section 3.3. For those of you who are interested, you can try it yourself by typing http://www.google.com/complete/search?output=toolbar&q=QUERY in a browser, where QUERY should be replaced by the particular query you are interested in.
Next, an XML parser will read the XML into memory and convert it into an XML DOM object that can be accessed with Javascript. It’s worth mentioning that different browsers have different built-in XML parsers, so it takes some extra code to make it work on all browsers. The code is present in the FAQ section 3.5. Suppose we load the XML file into an object called "doc", we can retrieve the suggestions by calling doc.getElementsByTagName(“suggestion”) and then invoking the method getAttribute(“data”) on the resulting array. We first cache the results so that if users backspace, it doesn't have to send another XMLHTTPRequest to Google server. The cache is essentially a two-dimensional array – an array of suggestions list with query as the key.
The results will then be taken to dynamically create a series of div and span elements that will form the suggestion list users see. The suggestion list is a div element, and each entry in the suggestion list is a span element. To line up the suggestion list perfectly with the input field, the script moves up the tree of offsetParents and adds the offsetTop and offsetLeft of each. Eventually, regardless of the actual composition of the offsetParent tree, this leads to the real coordinates of the input field on the screen. Here is a piece of code that recursively calculates the coordinates:

function calculateOffset(ref,attr)
{
  var os =0;
  
  while(ref)
  {
    os += ref[attr]; 
    ref = ref.offsetParent;
  }
  
  return os;
}

By passing the search box and its attributes ("offsetLeft" and "offsetTop") to the function, we can calculate the real coordinate of the inpt field. After taking into account the offsetHeight of the input field, we can easily find out where to position the suggestion list.

To allow for proper high-lighting, we also need to create event handlers for events like mouseover, mouseout, up arrow, down array, and tab key to allow users to select an entry in the list. This is achieved through changing the CSS style of span elements. Google has created different CSS classes for suggestion list and selected entry.

FAQ[]

What is the role of Javascript?[]

Google Suggest makes heavy use of AJAX technolgoies, and the following is a brief summary of these technologies and their corresponding roles:

CSS
- High-lighting of selected suggestion
XML
- Server sends the suggestions in XML format
XMLHTTPRequest
- Object for Asynchronous communication between Google Suggest back-end server and front-end interface
DOM
- Keypress Handler
  - up arrow: move up the cursor by changing the style/className of span
  - down arrow: move down the cursor by changing the style/className of span
  - tab key: fill the input field with the selected suggestion and hide the suggestion list
  - backspace key: if present in cache, display the cached suggestions; otherwise, send a new XMLHTTPRequest
- Mouse Handler
  - mouseover: high-light a suggestion by changing the className
  - mouseout: restore style by changing the className
  - mousedown: fill the input field with the selected suggestion and hide the suggestion list
- XMLHTTPRequest onreadystatechange Handler
  - dynamically display suggestion list
- XML Parser
  - parse the XML file retrieved from the server and make it accessible by the XMLHTTPRequest onreadystatechange handler
Javascript
- Make the above technologies possible

What parts of the interaction happen in the browser and what parts require server interaction?[]

Most of the interactions mentioned above happen in the browser, and only the AJAX request requires server interaction.

If data is fetched dynamically from the server, what is the granularity of those patches?[]

Server will send back a list of suggestions in XML format. The following is an example when you type "McC":

<?xml version="1.0"?>
<toplevel>
<CompleteSuggestion><suggestion data="mccain"/><num_queries int="76700000"/></CompleteSuggestion>
<CompleteSuggestion><suggestion data="mccain vp"/><num_queries int="13600000"/></CompleteSuggestion>
<CompleteSuggestion><suggestion data="mccain ad"/><num_queries int="13800000"/></CompleteSuggestion>
</toplevel>

Are there any special techniques for hiding latency?[]

Google Suggest added two techniques for avoiding/hiding latency -- timeout and cache.

The XMLHTTPRequest is not sent on each keystroke but instead a timeout mechnism is used to periodically check if the state of the input field has changed. This would handle fast typers on slow connections. For instance, if a user types 3 characters between timeouts, only a single request would go out to server.
If the state of the input field has changed between two timeouts, the program will first looks up the query in the cache it uses to store old results. If the result is present, no communication between server and browser is needed. This significantly reduces the lantency when users backspace. Only if the input field has changed, a XMLHTTPRequest will be sent to server.

Did the interaction have to contort itself to get around problems with the Web?[]

Because of incompatibility issues among browsers, the program often needs to make special case for each browser. For example, different browsers have different built-in XML parsers, so it takes some extra code to make it work on all browsers. The following code shows how to parse a XML file on both IE and Firefox:

// code for Windows
if (window.ActiveXObject)
{
  var doc=new ActiveXObject("Microsoft.XMLDOM");
  doc.async="false";
  doc.loadXML(XMLString);
}
// code for Mozilla, Firefox, Opera, etc.
else
{
  var parser=new DOMParser();
  var doc=parser.parseFromString(XMLString,"text/xml");
}