Generating query suggestions using contextual information

• US 8,209,347 B1
• Filed: 07/13/2011
• Issued: 06/26/2012
• Est. Priority Date: 08/01/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Sahami, Mehran, Heilman, Timothy D.
• Primary Examiner(s): Vital, Pierre
• Assistant Examiner(s): OBISESAN, AUGUSTINE KUNLE
• Application Number:
  US13/181,964
• Time in Patent Office: 349 Days
• Field of Search: None
• US Class Current: 707/767
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/353 into predefined classes

Abstract

A search engine receives a query from an end-user. The search engine executes the query on a content database and identifies a set of matching content. The search engine utilizes the matching content to generate a query vector describing the end-user query. The search engine searches a repository of other vectors, called “centroids,” to produce a ranked set of centroids matching the query vector. These centroids are converted into search queries and form a set of candidate queries. The search engine filters the candidate queries to identify ones that are likely to be meaningful to the end-user. The selected candidate queries are returned to the end-user as query suggestions.

Claims

1. A computer-implemented method, comprising:

receiving an original query;

selecting a plurality of documents responsive to the original query according to a ranking of the respective documents;

generating a plurality of term vectors, the plurality of term vectors including a term vector for each document;

truncating each term vector to include only highest-weighted terms from the respective document to provide a plurality of truncated term vectors;

combining the plurality of truncated term vectors containing the highest-weighted terms to produce a search query centroid;

searching a centroid repository for previously stored centroids matching the search query centroid;

converting each of a first number of the most highly-ranked centroids into a respective candidate query;

examining the candidate queries;

adding each candidate query to a set of query suggestions if the respective candidate query contains a threshold number of terms that are not included in the original query; and

providing the set of query suggestions in response to the original query.

2. The method of claim 1, wherein the search query centroid is a vector of the most common terms among the terms in the plurality of truncated term vectors.

3. The method of claim 1, wherein examining further includes examining the candidate queries in a ranked order.

4. The method of claim 1, further comprising:

calculating a dot product of each previously stored centroid and the search query centroid, the dot product indicating a degree of similarity between each previously stored centroid and the search query centroid; and

sorting the previously stored centroids by the respective dot products to produce a ranked list of centroids, where the most highly-ranked centroids most closely match the search query centroid.

5. The method of claim 1, further comprising:

adding the candidate query to the set of query suggestions when (|q_j|−

|q_j∩

z|>

0.5|z|∀

zε

(Z∪

{u})), where q_j represents terms in an examined candidate, z represents terms in the set of query suggestions Z, and {u} represents a set containing the set of terms in the original query.

6. The method of claim 1, wherein the set of query suggestions comprises a suggested query that is likely to be meaningful to an end-user.

7. The method of claim 1, further comprising:

generating a disjunction including an additional number of highest-weighted terms in the search query centroid;

wherein searching the centroid repository for previously stored centroids comprises searching the centroid repository for previously stored centroids that match the disjunction.

8. A system comprising:

a non-transitory storage device coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

receiving an original query;

selecting a plurality of documents responsive to the original query according to a ranking of the respective documents;

generating a plurality of term vectors, the plurality of term vectors including a term vector for each document;

truncating each term vector to include only highest-weighted terms from the respective document to provide a plurality of truncated term vectors;

combining the plurality of truncated term vectors containing the highest-weighted terms to produce a search query centroid;

searching a centroid repository for previously stored centroids matching the search query centroid;

converting each of a first number of the most highly-ranked centroids into a respective candidate query;

examining the candidate queries;

adding each candidate query to a set of query suggestions if the respective candidate query contains a threshold number of terms that are not included in the original query; and

providing the set of query suggestions in response to the original query.

9. The system of claim 8, wherein the search query centroid is a vector of the most common terms among the terms in the plurality of truncated term vectors.

10. The system of claim 8, wherein examining further includes examining the candidate queries in a ranked order.

11. The system of claim 8, further comprising:

calculating a dot product of each previously stored centroid and the search query centroid, the dot product indicating a degree of similarity between each previously stored centroid and the search query centroid; and

sorting the previously stored centroids by the respective dot products to produce a ranked list of centroids, where the most highly-ranked centroids most closely match the search query centroid.

12. The system of claim 8, wherein the operations further comprise:

adding the candidate query to the set of query suggestions when (|q_j|−

|q_j∩

z|>

0.5|z|∀

zε

(Z∪

{u})), where q_j represents terms in an examined candidate, z represents terms in the set of query suggestions Z, and {u} represents a set containing the set of terms in the original query.

13. The system of claim 8, wherein the set of query suggestions comprises a suggested query that is likely to be meaningful to an end-user.

14. The system of claim 8, wherein the operations further comprise:

generating a disjunction including an additional number of highest-weighted terms in the search query centroid;

wherein searching the centroid repository for previously stored centroids comprises searching the centroid repository for previously stored centroids that match the disjunction.

15. A computer program product having a non-transitory storage device having executable computer program instructions recorded thereon for providing suggestions to a client computer, the computer program instructions configured to implement a method comprising:

receiving an original query;

selecting a plurality of documents responsive to the original query according to a ranking of the respective documents;

generating a plurality of term vectors, the plurality of term vectors including a term vector for each document;

truncating each term vector to include only highest-weighted terms from the respective document to provide a plurality of truncated term vectors;

combining the plurality of truncated term vectors containing the highest-weighted terms to produce a search query centroid;

searching a centroid repository for previously stored centroids matching the search query centroid;

converting each of a first number of the most highly-ranked centroids into a respective candidate query;

examining the candidate queries;

adding each candidate query to a set of query suggestions if the respective candidate query contains a threshold number of terms that are not included in the original query; and

providing the set of query suggestions in response to the original query.

16. The computer program product of claim 15, wherein the search query centroid is a vector of the most common terms among the terms in the plurality of truncated term vectors.

17. The computer program product of claim 15, wherein examining further includes examining the candidate queries in a ranked order.

18. The computer program product of claim 15, wherein the operations further comprise:

calculating a dot product of each previously stored centroid and the search query centroid, the dot product indicating a degree of similarity between each previously stored centroid and the search query centroid; and

sorting the previously stored centroids by the respective dot products to produce a ranked list of centroids, where the most highly-ranked centroids most closely match the search query centroid.

19. The computer program product of claim 15, wherein the operations further comprise:

adding the candidate query to the set of query suggestions when (|q_j|−

|q_j∩

z|>

0.5|z|∀

zε

(Z∪

{u})), where q_j represents terms in an examined candidate, z represents terms in the set of query suggestions Z, and {u} represents a set containing the set of terms in the original query.

20. The computer program product of claim 15, wherein the set of query suggestions comprises a suggested query that is likely to be meaningful to an end-user.

21. The computer program product of claim 15, wherein the operations further comprise:

generating a disjunction including an additional number of highest-weighted terms in the search query centroid;

wherein searching the centroid repository for previously stored centroids comprises searching the centroid repository for previously stored centroids that match the disjunction.