Advertisement
  1. SEJ
  2.  ⋅ 
  3. Google Patents & Research Papers

How Autocomplete Works: The Patent Behind Google’s Query Completions

Learn about the query completion patent that helps Google predict the best autocomplete answers for a user's search query.

Query completions are a set of predictive suggestions that might appear when a searcher starts typing a query into a search box.

They offer searchers possible terms to search for based on what they start searching for, and are entirely optional.

Google granted a patent on query completions on June 30, 2021. Google has added information on help pages in the past about their use of query completions:

This patent relates to search engines, which aim to identify resources, such as webpages, images, text documents, and multimedia content like videos, relevant to a searcher’s information needs and present information about the resources in a most useful manner to the searcher.

Internet search engines generally return a set of search results (SERPs), each identifying a resource, in response to a searcher-submitted query.

Search systems that operate internet search engines can also provide query completions to searchers to help searchers satisfy their informational needs.

As used in this patent, the term “query completion” refers to a suggested sequence of terms that can get used as a query.

Some search systems may provide query completions in a list as the searcher is entering a query.

A searcher device interface for a search system typically sends input to the search system as the searcher enters each character of a query, and the search system provides query completions that match the entered characters.

The characters sent to the search system before the searcher enters a search command input, e.g., hitting the “Enter” key on an input keyboard or a “search” button on a searcher interface, may be referred to as a “query prefix.”

Once the query completions are received, the searcher device displays the query completions for searcher selection.

The searcher can select one of the query completions to submit the query completion to a search system without manually typing the query to enter the query.

An Example Query Prediction in SERPs

An example presentation of query completions is provided in a prior art way by a search system.

The example presentation includes a list of query completions provided for the one-character query prefix, “n.”

An example presentation of one-character query completions.Screenshot from Pdfpiw.uspto.gov, September 2021

The query prefix can be submitted to a search system by software of a graphical searcher interface of a web browser, or by software of a searcher interface of some other software application installed on a searcher device, such as a mobile application installed on a mobile computing device.

In response to receiving the query prefix, the search system can provide a search results page or other responsive data in a form presented on the searcher device.

The search results page can get provided as a markup language document, e.g., a HyperText Markup Language document.

The searcher device can render the document, e.g., using a web browser, to present the search results page on a display of the searcher device.

The search results page includes query completions that represent potential completions of the query prefix in a ranked order. The query completion, “news,” is ranked first.

Notably, the prior art search system may not consider a previous query when generating query completions or may only consider previously submitted queries that match the query prefix.

This may be so even if the searcher has shown a greater interest in babies and parenting, e.g., through previously submitted questions, or explicitly, e.g., through a searcher profile.

The search results page also includes search results, which may provide while the searcher is entering the query, in other words, before the searcher has is finished entering the query. Search results provided in this way will get referred to as “instant” search results.

A search system can obtain the search results by obtaining search results that satisfy the currently highest-ranked query completion.

In this example, the search results are for the highest-ranked query completion for query prefix, “basketball.”

This patent describes how a system can use a general-purpose action prediction engine to rank query completions based on how likely the query completions are to co-occur, in records of searcher activity of many searchers, with a query previously entered by the searcher.

A reference query can be used to search the records of searcher activity to identify likely query completions.

In general, one innovative aspect of the subject matter described in this specification can be embodied in methods that include:

  • Receiving a query prefix from a searcher.
  • Obtaining a reference parameter for the searcher.
  • Identifying likely queries that are likely to co-occur with the reference parameter in searcher activity sessions, wherein each likely query has an associated prediction score.
  • Determining a ranking of the likely queries according to the prediction scores.
  • Providing the ranking of the e likely queries in response to receiving the query prefix.

Reference Parameters for Query Completions

This patent can also include related computer systems, apparatus, and computer programs recorded on computer storage devices, each configured to perform the actions of the methods. The patent describes these additional features as optional ones.

It may use a reference parameter, which is a query previously submitted by the searcher. That reference parameter could be a:

  • Geographic location.
  • Language preference.
  • Interest associated with a searcher profile.

The actions behind reference parameters for query completions include:

  • Starting with initial scores of the likely queries.
  • Determining respective modified scores for the likely queries from the initial scores and the prediction scores of the likely queries.
  • Obtaining the initial scores of the likely queries comprises obtaining scores in a baseline collection of query completions for the query prefix.
  • Finding queries that are likely to co-occur with the reference parameter in searcher activity sessions comprises determining that the reference parameter and e characters of the query prefix correspond to an entry in a cache of likely queries, where each cache entry in the cache is associated with previously determined likely queries.
  • Gaining likely queries associated with the entry in the cache without performing a search of searcher activity sessions for the likely queries.

These actions include:

  • Receiving a second query prefix comprising a subsequent character to the query prefix.
  • Creating a key comprising the reference parameter and a subset of characters of the query prefix.
  • Deciding that the key corresponds to an entry in a cache of likely queries.
  • Returning likely queries associated with the entry in the cache of likely queries.
  • Filtering the likely queries according to the second query prefix that includes the subsequent character.

Identifying queries that are likely to co-occur with the reference parameter in searcher activity sessions comprises:

  • Finding a process has registered a search of searcher activity sessions for the likely queries based on the reference parameter and the query prefix, and after the process has completed the search of searcher activity sessions for the likely queries based on the reference parameter and the query prefix.
  • Obtaining likely queries from a result of the search.
  • Seeking queries that are likely to co-occur with the reference parameter in searcher activity sessions comprises providing, to leaf servers, a first character of the query prefix, wherein each leaf server returns, to an intermediate server or a root server, only likely queries that begin with the first character of the query prefix.
  • Analyzing whether the likely queries occur in a baseline collection of query completions.
  • Filtering any of the likely queries that do not occur in the baseline collection of query completions.
  • Making respective modified scores for the likely queries from the initial scores of the likely queries comprises computing a new ranking score for the likely query based on multiplying an initial ranking score of the likely query by a ranking factor.

The ranking factor R is given by:

.function..function. ##EQU00001## wherein P(x|q) is a measure of a likelihood of the likely query x occurring in (x) an activity session given that the reference parameter q also occurred in the same activity session, and P(x) is a measure of the likelihood of the likely query x appearing in an activity session.

Advantages Under This Query Completion Patent

  • More relevant and more personalized query completions.
  • Useful queries that they would not have otherwise seen.
  • A prediction engine using a cache can improve system performance and prevent a prediction engine from doing overly duplicative searching.
  • A prediction engine filtering at leaf servers reduces the amount of information exchanged between servers..
  • Filtering by only a subset of characters of the query prefix can reduce response latency.

This query completion patent can be found at:

Query completions
Inventors: Emanuel Taropa, and Ishai Rabinovitz
Assignee: GOOGLE LLC
US Patent: 10,698,901
Granted: June 30, 2020
Filed: March 27, 2017

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for ranking query completions based on activity session data. One of the methods includes receiving a query prefix from a searcher. A reference parameter for the searcher is obtained. Likely queries that are likely to co-occur with the reference parameter in searcher activity sessions are identified, wherein each likely query has an associated prediction score. A ranking of the likely queries is provided in response to receiving the query prefix.

This query completion patent tells us that a search system can improve query completions by considering information about a searcher. These can include a query previously submitted by the searcher.

A previously submitted query can indicate the interests of the searcher, particularly of the present interests of the searcher, which can be useful when determining relevant query completions for a potentially short query prefix that may be devoid of other information.

Query Completions Provided by a Search System

The example presentation includes a list of query completions provided for the one-character query prefix, “n.”

In this example, it gets assumed that the searcher previously submitted the query “infant clothing.”

The search system can use this information to provide more relevant, practical, or personalized query completions for the searcher using the techniques described below.

For example, a search system may determine that a searcher who has recently entered the query “infant clothing” is more likely to be currently interested in baby clothes than in the news. Thus, the search system can generate query completions possible to co-occur in searcher activity data with the previous query “infant clothing.”

For example, the search system can determine that the query completion “newborn clothing” and the query completion “newborn baby clothes” are likely to co-occur in searcher activity data with the previous query “infant clothing.”

The query completions may not have otherwise appeared among many top-ranked query completions had the last query not been considered.

So previous queries can influence what shows in a query completion at Google.

Query completion engine.Screenshot from Pdfpiw.uspto.gov, September 2021

Serving query completions determined by looking at previous queries also result in the search system providing more relevant search results for a query prefix.

For example, the search results obtained for the query “newborn clothing” are more likely to be considered appropriate by a searcher whose previous query was “infant clothing” than search results related to the news.

The search system allows searchers to control whether their previously submitted queries get stored by the system as queries are associated with how long they are stored and whether they get used in generating query completions.

Takeaways for Query Completion

This patent goes on to explain how caching, and the identification of likely query suggestions takes place.

It’s good to know Google’s information regarding query completions, especially if you optimize pages for the query terms that a search engine might rank pages.

Someone starting to search for what you offer may see results that differ based on reference parameters that could influence their search results.

These reference parameters can include geographic location, language preference, interest associated with a searcher profile, and previously searched for queries.

What query completions might pages that you are building get found?

More Resources:


Featured image: Dilen/Shutterstock

ADVERTISEMENT
Bill Slawski Director of SEO Research at Go Fish Digital

Bill Slawski had been doing SEO since 1996. He was a legal and technical administrator at the highest trial level ...

How Autocomplete Works: The Patent Behind Google’s Query Completions

Subscribe To Our Newsletter.

Conquer your day with daily search marketing news.