Ranking search results based on similar queries

• US 9,009,146 B1
• Filed: 05/21/2012
• Issued: 04/14/2015
• Est. Priority Date: 04/08/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Lopatenko, Andrei, Kim, Hyung-Jin, Dornbush, Sandor, Lopyrev, Mikhail, Wei, Leonard, Kilbourn, Timothy P.
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): HUTTON, NAN
• Application Number:
  US13/476,875
• Time in Patent Office: 1,058 Days
• Field of Search: 707/723, 707/748
• US Class Current: 707/723
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

In general, in one aspect, embodiments of the invention feature a computer-implemented method for providing input to a document ranking process for ranking a plurality of documents, the document ranking process taking as input a quality of result statistic for an individual document in the plurality of documents, the plurality of documents having been identified in response to a query, the quality of results statistic being for the query and the individual document. The method for providing input can include, for a first document identified as a search result of a user-submitted query, scoring one or more other queries based upon a similarity to the user-submitted query, each of the one or more other queries being different from the user-submitted query.

Claims

1. A computer-implemented method comprising:

for a document identified as a search result of a user-submitted query, scoring one or more other queries based upon a similarity to the user-submitted query, each of the one or more other queries being different from the user-submitted query, where scoring the one or more other queries comprises;

receiving optional terms, regular terms, and stopword terms of the user-submitted query;

receiving an optional-term weight, a regular-term weight; and

a stopword-term weight;

receiving terms of the one or more other queries;

determining for each of the other queries whether the other query includes an exact match for each required term in the user-submitted query and, if not, removing the other query from consideration; and

determining a respective match score for each of the other queries not removed from consideration, including adjusting the respective score by the regular-term weight for each regular term of the user-submitted query that appears in the other query, adjusting the respective score by the optional-term weight for each optional term of the user-submitted query that appears in the other query, and adjusting the respective score by the stopword-term weight for each stopword term of the user-submitted query that appears in the other query, wherein all operations of adjusting by a weight are the same operation, and all operations of adjusting either add the weight to the respective match score or multiply the respective match score by the weight; and

determining a respective score for each other query not removed from consideration from the match score for the other query;

selecting one or more of the other queries based on each of the respective scores of the other queries;

deriving a quality of result statistic for the document from respective data associated with the selected queries, the respective data being indicative of prior user interaction with the document when the document was provided as a search result for the selected queries; and

providing the quality of result statistic as the quality of result statistic input to a document ranking process for the user-submitted query, the document ranking process configured to rank a plurality of documents responsive to the user-submitted query.

2. The method of claim 1 in which one of the respective scores is decreased by a penalty amount when terms in a corresponding one of the other queries are in a different order than the terms in the user-submitted query.

3. The method of claim 1 in which selecting one or more of the other queries comprises selecting one query having a greatest respective score.

4. The method of claim 1 in which the respective data is aggregated click data.

5. The method of claim 1, further comprising limiting the quality of result statistic for the document according to a threshold.

6. The method of claim 1, further comprising reducing the quality of result statistic for the document by an amount based upon a degree of dissimilarity between the document and at least one of the terms in the user-submitted query.

7. The method of claim 1 in which deriving the quality result statistic further comprises weighting the respective data associated each of the selected queries by the respective scores for each of the selected queries and aggregating the weighted respective data.

8. The method of claim 1, further comprising:

determining a penalty based upon the user-submitted query containing a compound term that is broken in one or more of the other queries; and

applying the determined penalty to one or more of the respective scores for the one or more other queries.

9. The method of claim 1, wherein, for at least one of the other queries not excluded from consideration, determining a respective score comprises:

calculating a multiplicative match score and an absolute match score for each of the other queries not removed from consideration based on the weights, where the multiplicative match score is determined based on multiplication of the weights and wherein the absolute match score is determined based on addition of the weights;

determining whether to use the absolute match score, the multiplicative match score, or a combination thereof as the respective score for each of the other queries not removed from consideration based on a comparison of lengths of the user-input query and the other query; and

based on the determination of whether to use the absolute match score, the multiplicative match score, or the combination thereof, calculating the respective score for the other queries not removed from consideration using the absolute match score, the multiplicative match score, or the combination thereof.

10. The method of claim 9 in which the combination of the absolute match score and the multiplicative match score is determined by linearly approximating a difference between the absolute match score and the multiplicative match score.

11. The method of claim 1 where scoring the one or more other queries comprises:

receiving one or more variant terms of the user-submitted query and one or more variants of each of the variant terms; and

receiving, for each variant term and for each variant of the variant term, an associated variant-term weight;

wherein determining a respective score for the other queries not removed from consideration further includes adding to the respective score the variant-term weight for each variant term that appear in the other query.

12. A computer program product encoded on a non-transitory computer-readable medium, operable to cause data processing apparatus to perform operations comprising:

for a document identified as a search result of a user-submitted query, scoring one or more other queries based upon a similarity to the user-submitted query, each of the one or more other queries being different from the user-submitted query, where scoring the one or more other queries comprises;

receiving optional terms, regular terms, and stopword terms of the user-submitted query;

receiving an optional-term weight, a regular-term weight; and

a stopword-term weight;

receiving terms of the one or more other queries;

determining for each of the other queries whether the other query includes an exact match for each required term in the user-submitted query and, if not, removing the other query from consideration;

determining respective match score for each of the other queries not removed from consideration, including adjusting the respective score by the regular-term weight for each regular term of the user-submitted query that appears in the other query, adjusting the respective score by the optional-term weight for each optional term of the user-submitted query that appears in the other query, and adjusting the respective score by the stopword-term weight for each stopword term of the user-submitted query that appears in the other query, wherein all operations of adjusting by a weight are the same operation, and all operations of adjusting either add the weight to the respective match score or multiply the respective match score by the weight; and

determining a respective score for each other query not removed from consideration from the match score for the other query;

selecting one or more of the other queries based on each of the respective scores of the other queries;

deriving a quality of result statistic for the document from respective data associated with the selected queries, the respective data being indicative of prior user interaction with the document when the document was provided as a search result for the selected queries; and

providing the quality of result statistic as the quality of result statistic input to a document ranking process for the user-submitted query, the document ranking process configured to rank a plurality of documents responsive to the user-submitted query.

13. The computer program product of claim 12 in which one of the respective scores is decreased by a penalty amount when terms in a corresponding one of the other queries are in a different order than the terms in the user-submitted query.

14. The computer program product of claim 12 in which deriving the quality result statistic further comprises weighting the respective data associated each of the selected queries by the respective scores for each of the selected queries and aggregating the weighted respective data.

15. The computer program product of claim 12, wherein, for at least one of the other queries not excluded from consideration, determining a respective score comprises:

calculating a multiplicative match score and an absolute match score for each of the other queries not removed from consideration based on the weights, where the multiplicative match score is determined based on multiplication of the weights and wherein the absolute match score is determined based on addition of the weights;

determining whether to use the absolute match score, the multiplicative match score, or a combination thereof as the respective score for each of the other queries not removed from consideration based on a comparison of lengths of the user-input query and the other query; and

based on the determination of whether to use the absolute match score, the multiplicative match score, or the combination thereof, calculating the respective score for the other queries not removed from consideration using the absolute match score, the multiplicative match score, or the combination thereof.

16. The computer program product of claim 12 where scoring the one or more other queries comprises:

receiving one or more variant terms of the user-submitted query and one or more variants of each of the variant terms; and

receiving, for each variant term and for each variant of the variant term, an associated variant-term weight;

wherein determining a respective score for the other queries not removed from consideration further includes adding to the respective score the variant-term weight for each variant term that appear in the other query.

17. A system for providing input to a document ranking process for ranking a plurality of documents, the system comprising:

one or more servers;

an interface to the one or more servers that is configured to receive an indication of a document identified as a search result of a user-submitted query;

a query scoring engine installed on the one or more servers that is configured to, for the document identified as a search result of the user-submitted query, score one or more other queries based upon a similarity to the user-submitted query, each of the one or more other queries being different from the user-submitted query, where scoring the one or more other queries comprises;

receiving optional terms, regular terms, and stopword terms of the user-submitted query;

receiving an optional-term weight, a regular-term weight; and

a stopword-term weight;

receiving terms of the one or more other queries;

determining for each of the other queries whether the other query includes an exact match for each required term in the user-submitted query and, if not, removing the other query from consideration;

determining a respective match score for each of the other queries not removed from consideration, including adjusting the respective score by the regular-term weight for each regular term of the user-submitted query that appears in the other query, adjusting the respective score by the optional-term weight for each optional term of the user-submitted query that appears in the other query, and adjusting the respective score by the stopword-term weight for each stopword term of the user-submitted query that appears in the other query, wherein all operations of adjusting by a weight are the same operation, and all operations of adjusting either add the weight to the respective match score or multiply the respective match score by the weight; and

determining a respective score for each other query not removed from consideration from the match score for the other query;

wherein the query scoring engine is further configured to select one or more of the other queries based on each of the respective scores of the other queries; and

a rank modifier engine installed on the one or more servers that is configured to derive a quality of result statistic for the document from respective data associated with the selected queries, the respective data being indicative of prior user interaction with the document when the document was provided as a search result for the selected queries, wherein the rank modifier engine is further configured to provide the quality of result statistic as the quality of result statistic input to a document ranking process for the user-submitted query, the document ranking process configured to rank a plurality of documents responsive to the user-submitted query.

18. The system of claim 17 in which one of the respective scores is decreased by a penalty amount when terms in a corresponding one of the other queries are in a different order than the terms in the user-submitted query.

19. The system of claim 17, wherein, for at least one of the other queries not excluded from consideration, determining a respective score comprises:

calculating a multiplicative match score and an absolute match score for each of the other queries not removed from consideration based on the weights, where the multiplicative match score is determined based on multiplication of the weights and wherein the absolute match score is determined based on addition of the weights;

determining whether to use the absolute match score, the multiplicative match score, or a combination thereof as the respective score for each of the other queries not removed from consideration based on a comparison of lengths of the user-input query and the other query; and

based on the determination of whether to use the absolute match score, the multiplicative match score, or the combination thereof, calculating the respective score for the other queries not removed from consideration using the absolute match score, the multiplicative match score, or the combination thereof.

20. The system of claim 17 in which where scoring the one or more other queries comprises:

receiving one or more variant terms of the user-submitted query and one or more variants of each of the variant terms; and

receiving, for each variant term and for each variant of the variant term, an associated variant-term weight;

wherein determining a respective score for the other queries not removed from consideration further includes adding to the respective score the variant-term weight for each variant term that appear in the other query.