Re-ranking search results based on query log

• US 7,818,315 B2
• Filed: 03/13/2006
• Issued: 10/19/2010
• Est. Priority Date: 03/13/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhuang, Ziming, Cucerzan, Silviu-Petru
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Lee; Rachel J
• Application Number:
  US11/374,361
• Publication Number:
  US 20070214131A1
• Time in Patent Office: 1,681 Days
• Field of Search: None
• US Class Current: 707/723
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A system(s) and/or method(s) that facilitate improving the relevance of search results through utilization of a query log. The relevance of the search results for a target query can be judged based on one or more queries in the log that are related to the target query temporally and/or lexically. The diversity of the top-ranked search results can be increased and/or decreased based on an iterative re-ranking process of the search result set.

Claims

1. A system that facilitates re-ranking search results retrieved by a search engine, comprising one or more computers configured with:

a query log component that, responsive to a target query, builds a language model specific to the target query based on queries stored in a query log of a search engine, the query log component comprising;

a compilation module that determines absolute frequencies of search terms corresponding to the queries related lexically including a number of queries submitted by users that include the target query, and

a session module that determines relative frequencies of the queries related temporally and submitted during a user session;

a matching component that compares a lexical property of an initial search result for the target query and the language model and computes a match score that indicates a probability that two or more search results are related by utilizing a cosine similarity and a KL-divergence for comparing;

a ranking component that re-ranks a subset of the initial search result based on the match score and a rank of the initial search result, wherein the re-ranking of the subset of the initial search result comprises processing a URL, one or more page titles, a plurality of page content and a plurality of snippets resulting from a document query pairing, and further wherein, the plurality of snippets are search-engine dependent;

a user control selection component that allows a user to further re-rank the initial search result, wherein the user control selection component is configured to accept user input to manually control the further re-ranking of the initial search result; and

a user control component that applies a selectable modification to at least one of the system components to change the re-ranking of the subset of the initial search result and the selectable modification is one of an increase in a diversity of top re-ranked search results and a decrease in the diversity of the top re-ranked search results.

2. The system of claim 1, the query log component utilizes at least one of a temporal similarity measure and a lexical similarity measure of the target query and the queries stored in the query log.

3. The system of claim 1, the diversity of the top re-ranked search results is controlled by an iterative re-ranking scheme in which one search result is selected to be added to the re-ranked results in each iteration and a discounting scheme is applied to the language model to decrease a similarity of the language model to the selected search result.

4. The system of claim 1, the query log component utilizes the absolute frequencies and the relative frequencies of the queries in the query log to derive the language model.

5. The system of claim 1, the language model is a probability distribution over query terms extracted from the queries in the query log.

6. The system of claim 5, the query terms are extracted from at least one of a set of queries that contain the target query as a substring, a set of queries that have a large lexical overlap with the target query, a set of queries that preceded the target query in a user search session, and a set of queries that followed the target query in a user search session.

7. The system of claim 1, the matching component uses the language model to assign the match score to a search result based on how the search result matches at least one of:

a title of a document returned as the search result, a text of the document, a URL, a snippet generated by the search engine for a document query pair.

8. A method for providing relevant information based on an initial query, comprising using one or more processors to perform the following computer-executable acts:

receiving an initial set of ranked search results in response to the initial query;

responsive to the initial query, using a query log to build a query-specific language model for the initial query, the query log comprising a compilation module that determines absolute frequencies of search terms corresponding to queries lexically related, including a number of queries submitted by users that contain a target query search term, and a session module that determines relative frequencies of temporally related queries submitted during a user session;

comparing the language model with a lexical property of the initial set of ranked search results to compute a match score that indicates a probability that two or more search results are related by utilizing a cosine similarity and a KL-divergence for comparing;

re-ranking the initial set of ranked search results based on the match score, wherein the re-ranking of the initial set of ranked search results comprises processing a URL, one or more page titles, a plurality of page content and a plurality of snippets resulting from a document query pairing, and further wherein, the plurality of snippets are search-engine dependent;

receiving a user input to further re-rank the initial set of ranked search results, wherein the user input manually controls the further re-ranking of the initial set of ranked search results; and

the further re-ranking of the initial set of ranked search results comprising one of;

increasing a diversity of the re-ranked search results and decreasing the diversity of the re-ranked search results and increasing or decreasing the diversity of the re-ranked search results is based on a received user-selectable criteria.

9. The method of claim 8, building the language model for the initial query is based on the temporally related queries.

10. The method of claim 8, building the language model for the initial query is based on the lexically related queries.

11. The method of claim 8, further comprising utilizing an iterative and a discounting scheme to control the diversity of the re-ranked search results.

12. The method of claim 8, building the language model comprising utilizing a frequency of queries in the query log.

13. A computer-readable storage medium including instructions to perform a method that comprises:

receiving an initial set of search results from a target query;

analyzing properties of the initial set of search results;

comparing the properties of the initial set of search results with at least one property of another set of search results to compute a match score by utilizing a cosine similarity and a KL-divergence;

re-ranking of the initial set of search results based on the compared properties of the initial set of search results and the another set of search results, the providing a re-ranking including applying a weighting factor to queries temporally adjacent to the target query and to extensions of the target query, wherein the re-ranking of the initial set of ranked search results comprises processing a URL, one or more page titles, a plurality of page content and a plurality of snippets resulting from a document query pairing, and further wherein, the plurality of snippets are search-engine dependent;

outputting a modified set of search results and the re-ranking;

applying a user input interactively to increase a diversity of the modified set of search results or decrease the diversity of the modified set of search results;

assigning a ranking score to the queries temporally adjacent to the target query and another ranking score to the extensions of the target query;

summing the ranking score and the another ranking score to form a sum; and

dividing the sum by an initial document ranking, to bias the re-ranking toward the initial document ranking.

14. The computer-readable storage medium of claim 13, the method further comprising:

selectively receiving a modification to the re-ranking; and

tailoring the re-ranking based on the received modification.

15. The computer-readable storage medium of claim 13, the method further comprising comparing the initial set of search results with the another set of search results applies one of a temporal comparison and a lexical comparison.

16. A method comprising using one or more processors to perform the following computer-executable acts:

receiving a target query input to a search engine;

obtaining search results of the target query;

obtaining at least two sources of information from a query log component, a first source being compilation data from search query input from a plurality of users and a second source being session data obtained during a user session;

analyzing the compilation data to obtain queries that are related lexically;

determining an absolute frequency of the lexically-related queries corresponding to a number of queries that include the target query submitted by the plurality of users;

analyzing the session data to obtain queries that are related temporally;

aggregating the analyzed session data with analyzed session data from other user sessions;

determining an occurrence rate of the temporally-related queries across the aggregated user sessions;

extracting query terms from a set of queries including queries that contain the target query as a substring, queries that have a large lexical overlap with the target query, queries that preceded the target query in the user session, and queries that followed the target query in the user session;

creating a query-specific language model for the target query based on the extracted query terms, the query-specific language model derived from the absolute frequency of the lexically-related queries and the occurrence rate of the temporally-related queries across the aggregated user sessions;

comparing the query-specific language model to a language model for every search result of the search results, the comparing utilizing a cosine similarity and a KL-divergence;

re-ranking the search results based on a result of the comparing, wherein the re-ranking of the search results comprises processing a URL, one or more page titles, a plurality of page content and a plurality of snippets resulting from a document query pairing, and further wherein, the plurality of snippets are search-engine dependent; and

receiving a user input to further re-rank the search results, wherein the user input manually controls the further re-ranking of the search results;

outputting a final re-ranked search results to a user; and

interactively providing the user input to change a ranking of the final re-ranked search results to increase or decrease a diversity of the final re-ranked search results.