Search queries improved based on query semantic information

• US 8,577,907 B1
• Filed: 09/24/2011
• Issued: 11/05/2013
• Est. Priority Date: 03/03/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Singhal, Amit, Sahami, Mehran, Lamping, John, Kaszkiel, Marcin, Henzinger, Monika H
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Pham, Michael
• Application Number:
  US13/244,368
• Time in Patent Office: 773 Days
• Field of Search: 707/759
• US Class Current: 707/759
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence

Abstract

A search query for a search engine may be improved by incorporating alternate terms into the search query that are semantically similar to terms of the search query, taking into account information derived from the search query. An initial set of alternate terms that may be semantically similar to the original terms in the search query is generated. The initial set of alternate terms may be compared to information derived from the original search query. One example of such information is a set of documents retrieved in response to a search performed using the initial search query. One or more of the alternate terms may be added to the original search query based on their relationship to the information derived from the original search query.

Claims

1. A computer-implemented method comprising:

receiving, by a search system, a search query;

generating, by the search system, a potential substitute term that is related to a query term of the search query;

identifying, by the search system, an original set of documents that are responsive to the search query;

weighting each potential substitute term that appears in a document in the original set based on a prevalence of the potential substitute term in the original set of documents;

producing a pruned set of terms whose weight satisfies a condition;

determining that the potential substitute term is a member of the pruned set of terms; and

in response to determining that the potential substitute term is a member of the pruned set of terms, modifying, by the search system, the search query to include the potential substitute term.

2. The method of claim 1, further comprising performing a search for documents based on the modified search query.

3. The method of claim 1, wherein the pruned set of terms contains terms whose weight is greater than zero.

4. The method of claim 1, wherein the pruned set of terms contains terms whose weight is greater than a threshold weight.

5. The method of claim 1, wherein a number of documents in the original set of documents is limited to a specific number of the most relevant documents.

6. The method of claim 1, wherein weighting each potential substitute term comprises using inverse document frequency to measure the prevalence of the substitute term.

7. The method of claim 1, wherein weighting each potential substitute term comprises using a number of times the potential substitute terms appears in the original set of documents to measure the prevalence of the substitute term.

8. A system comprising:

one or more computers and one or more storage devices storing instructions that are configured, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

receiving a search query;

generating a potential substitute term that is related to a query term of the search query;

identifying an original set of documents that are responsive to the search query;

weighting each potential substitute term that appears in a document in the original set based on a prevalence of the potential substitute term in the original set of documents;

producing a pruned set of terms whose weight satisfies a condition;

determining that the potential substitute term is a member of the pruned set of terms; and

in response to determining that the potential substitute term is a member of the pruned set of terms, modifying the search query to include the potential substitute term.

9. The system of claim 8, wherein the operations further comprise performing a search for documents based on the modified search query.

10. The system of claim 8, wherein the pruned set of terms contains terms whose weight is greater than zero.

11. The system of claim 8, wherein the pruned set of terms contains terms whose weight is greater than a threshold weight.

12. The system of claim 8, wherein a number of documents in the original set of documents is limited to a specific number of the most relevant documents.

13. The system of claim 8, wherein weighting each potential substitute term comprises using inverse document frequency to measure the prevalence of the substitute term.

14. The system of claim 8, wherein weighting each potential substitute term comprises using a number of times the potential substitute terms appears in the original set of documents to measure the prevalence of the substitute term.

15. A non-transitory computer-readable storage device storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

receiving a search query;

generating a potential substitute term that is related to a query term of the search query;

identifying an original set of documents that are responsive to the search query;

weighting each potential substitute term that appears in a document in the original set based on a prevalence of the potential substitute term in the original set of documents;

producing a pruned set of terms whose weight satisfies a condition;

determining that the potential substitute term is a member of the pruned set of terms; and

in response to determining that the potential substitute term is a member of the pruned set of terms, modifying the search query to include the potential substitute term.

16. The non-transitory computer-readable storage device of claim 15, wherein the operations further comprise performing a search for documents based on the modified search query.

17. The non-transitory computer-readable storage device of claim 15, wherein the pruned set of terms contains terms whose weight is greater than zero.

18. The non-transitory computer-readable storage device of claim 15, wherein the pruned set of terms contains terms whose weight is greater than a threshold weight.

19. The non-transitory computer-readable storage device of claim 15, wherein a number of documents in the original set of documents is limited to a specific number of the most relevant documents.

20. The non-transitory computer-readable storage device of claim 15, wherein weighting each potential substitute term comprises using inverse document frequency to measure the prevalence of the substitute term.

21. The non-transitory computer-readable storage device of claim 15, wherein weighting each potential substitute term comprises using a number of times the potential substitute terms appears in the original set of documents to measure the prevalence of the substitute term.