Auto-detection of historical search context

• US 8,972,397 B2
• Filed: 03/11/2010
• Issued: 03/03/2015
• Est. Priority Date: 03/11/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Imig, Scott K., Apacible, Johnson T., Bala, Aravind, Bailey, Peter R., Geetha, Gayathri Ravichandran, Rounthwaite, Robert L., Yang, Hung-chih
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Kim, Paul
• Application Number:
  US12/721,565
• Publication Number:
  US 20110225192A1
• Time in Patent Office: 1,818 Days
• Field of Search: 707/732, 707/723, 707/706
• US Class Current: 707/732
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Architecture that automatically detects historical search contexts as well as behaviors related to a search query. Machine learning and hand-authored rules are employed to automatically identify search contexts. Historical information likely to be useful in the current context is surfaced. When a user enters a search query or executes another search behavior, past behaviors are exposed which are contextually related to the current behavior. The architecture also provides automatic discovery of historical contexts, features related to the contexts, and training or authoring of a system for classifying behavior into contexts, using some combination of the machine learning and/or hand-authored rules. A runtime system classifies the current user behavior into a context and surfaces contextual information to the user.

Claims

1. A volatile memory, non-volatile memory, optical disk, or hard drive storing computer-executable instructions which, when executed by a computer, cause the computer to perform acts comprising:

representing historical user behaviors of a user using a set of features, the set of features including click features and query features;

training a classifier using training data comprising values for the features to identify a plurality of historical search contexts, wherein the plurality of historical search contexts include;

a first historical search context having first values for the features, wherein the first values include;

first click feature values for the click features, the first click feature values representing multiple first clicks entered by the user on multiple different first uniform resource locators (URLs) as part of the first historical search context, and

first query feature values for the query features, the first query feature values representing multiple different first queries entered by the user as part of the first historical search context,

a second historical search context having second values for the features, wherein the second values include;

second click feature values for the click features, the second click feature values representing multiple second clicks entered by the user on multiple different second URLs as part of the second historical search context, and

second query feature values for the query features, the second query feature values representing multiple different second queries entered by the user as part of the second historical search context;

representing current user behavior during a current user session using third values for the features, wherein the third values include current click feature values for the click features and current query feature values for the query features, the current click feature values representing multiple current clicks entered by the user on multiple different current URLs during a current session and the current query feature values representing multiple different current queries entered by the user during the current session;

during the current user session, determining that the current user behavior is relatively more similar to the first historical search context than the second historical search context, wherein the determining comprises;

using the first click feature values, the second click feature values, and the current click feature values to analyze similarity of the multiple different current URLs clicked by the user during the current session to the multiple different first URLs clicked by the user as part of the first historical search context and the multiple different second URLs clicked by the user as part of the second historical search context, and

using the first query feature values, the second query feature values, and the current query feature values to analyze similarity of the multiple current queries entered by the user during the current session to the multiple different first queries entered by the user as part of the first historical search context and the multiple different second queries entered by the user as part of the second historical search context; and

surfacing the first historical search context as part of the current session for the user.

4. The physical storage media of claim 1, the acts further comprising:

creating a click graph representing the multiple first clicks and the multiple second clicks, the click graph having a first terminal state representing a first web page labeled as a first category and a second terminal state representing a second web page labeled as a second category;

performing a first random walk over the click graph for an individual first click to reach the first terminal state;

responsive to reaching the first terminal state via the first random walk, tagging the individual first click with the first category as an individual first click feature value;

performing a second random walk over the click graph for an individual second click to reach the second terminal state;

responsive to reaching the second terminal state via the second random walk, tagging the individual second click with the second category as an individual second click feature value.

5. The physical storage media of claim 1, the acts further comprising:

creating a click graph representing the multiple first clicks and the multiple second clicks, the click graph having a first terminal state representing a first web page labeled as a first category and a second terminal state representing a second web page labeled as a second category;

performing a first random walk over the click graph for an individual first query to reach the first terminal state;

responsive to reaching the first terminal state via the first random walk, tagging the individual first query with the first category as an individual first query feature value;

performing a second random walk over the click graph for an individual second query to reach the second terminal state; and

responsive to reaching the second terminal state via the second random walk, tagging the individual second query with the second category as an individual second query feature value.

6. The physical storage media of claim 1, the acts further comprising:

determining that an individual first URL is the most-frequently clicked URL for an individual first query entered by the user as part of the first historical search context; and

tagging the individual first query with the individual first URL as an individual first query feature value;

determining that an individual second URL is the most-frequently clicked URL for an individual second query entered by the user as part of the second historical search context; and

tagging the individual second query with the individual second URL as an individual second query feature value.

7. The physical storage media of claim 1, the acts further comprising:

determining that an individual first domain is the most-frequently clicked domain for an individual first query entered by the user as part of the first historical search context;

tagging the individual first query with the individual first domain as an individual first query feature value;

determining that an individual second domain is the most-frequently clicked domain for an individual second query entered by the user as part of the second historical search context; and

tagging the individual second query with the individual second domain as an individual second query feature value.

8. The physical storage media of claim 1, wherein the determining comprises:

determining a first Levenshtein distance between an individual current query entered by the user during the current session and an individual first query entered by the user as part of the first historical search context; and

determining a second Levenshtein distance between the individual current query entered by the user during the current session and an individual second query entered by the user as part of the second historical search context.

9. The physical storage media of claim 1, the acts further comprising:

highlighting at least one word in an individual first query entered by the user as part of the first historical search context that is not present in an individual current query entered by the user during the current session.

10. The physical storage media of claim 1, the acts further comprising:

updating the training of the classifier based on at least one subsequent click entered by the user after surfacing the first historical search context during the current user session.

11. The physical storage media of claim 1, wherein the surfacing comprises displaying, during the current user session, the multiple first queries entered by the user as part of the first historical search context.

12. The physical storage media of claim 11, wherein the surfacing comprises displaying, during the current user session:

an individual first URL that was returned in response to an individual first query and clicked on by the user as part of the first historical search context, and

another individual first URL that was returned in response to another individual first query and clicked on by the user as part of the first historical search context.

2. A method performed by at least one computing device, the method comprising:

receiving a current search query from a user during a current user session having associated current user behavior;

analyzing a search history for one or more historical search contexts by applying similarity analysis to the current search query and historical queries in the search history;

detecting an individual historical search context to use as a current search context by relating tagged historical user behaviors associated with the individual historical search context to the current user behavior that is associated with the current user session;

presenting the current search context for user interaction, including presenting individual historical queries from the detected individual historical search context; and

responsive to the user hovering over a first one of the individual historical queries for the detected individual historical search context, presenting individual URLs that were historically clicked on for the first individual historical query that is being hovered over.

3. The method according to claim 2, further comprising providing feedback for tuning the detecting based on the hovering, the tuning being performed by training a classifier used for the detecting.

13. A system comprising:

at least one processing unit; and

one or more physical storage media storing computer-executable instructions which, when executed by the at least one processing unit, cause the at least one processing unit to;

represent historical user behaviors of a user using a set of features, the set of features including click features and query features;

train a classifier using training data comprising values for the features to identify a plurality of historical search contexts, wherein the plurality of historical search contexts include;

a first historical search context having first values for the features, wherein the first values include;

first click feature values for the click features, the first click feature values representing multiple first uniform resource locators (URLs) clicked on by the user as part of the first historical search context, and

first query feature values for the query features, the first query feature values representing multiple first queries entered by the user as part of the first historical search context,

a second historical search context having second values for the features, wherein the second values include;

second click feature values for the click features, the second click feature values representing multiple second URLs clicked on by the user as part of the second historical search context, and

second query feature values for the query features, the second query feature values representing multiple second queries entered by the user as part of the second historical search context;

represent current user behavior during a current user session using third values for the features, wherein the third values include current click feature values for the click features and current query feature values for the query features, the current click feature values representing multiple current URLs clicked on by the user during a current session and the current query feature values representing multiple current queries entered by the user during the current session;

during the current user session, determine that the current user behavior is relatively more similar to the first historical search context than the second historical search context, wherein the determining comprises analyzing similarity of;

the current click feature values to the first click feature values and the second click feature values, and

the current query feature values to the first query feature values and the second query feature values; and

surface the first historical search context as part of the current session for the user.

14. The system of claim 13, wherein the computer-executable instructions further cause the processing unit to:

tag an individual first query entered by the user as part of the first historical search context based on a first vertical search engine to which the individual first query was submitted by the user as part of the first historical search context; and

tag an individual second query entered by the user as part of the second historical search context based on a second vertical search engine to which the individual second query was submitted by the user as part of the second historical search context.

15. The system of claim 14, wherein the computer-executable instructions further cause the processing unit to:

tag an individual current query entered by the user during the current user session based on a third vertical search engine to which the individual current query was submitted by the user.

16. The system of claim 13, wherein the computer-executable instructions further cause the processing unit to:

tag an individual first query entered by the user as part of the first historical search context with a first time of day when the individual first query was submitted; and

tag an individual second query entered by the user as part of the second historical search context with a second time of day when the individual second query was submitted,

wherein the first time of day is morning and the second time of day is evening.

17. The system of claim 13, wherein the computer-executable instructions further cause the processing unit to:

tag an individual first query entered by the user as part of the first historical search context with a first location from which the individual first query was submitted; and

tag an individual second query entered by the user as part of the second historical search context with a second location from which the individual second query was submitted,

wherein the second location is different than the first location.

18. The system of claim 13, wherein the computer-executable instructions further cause the processing unit to:

tag an individual first query entered by the user as part of the first historical search context with a first device from which the individual first query was submitted; and

tag an individual second query entered by the user as part of the second historical search context with a second device from which the individual second query was submitted,

wherein the first device and the second device are different devices.

19. The system of claim 13, wherein the computer-executable instructions further cause the processing unit to:

tag an individual first query entered by the user as part of the first historical search context with a first seasonal time when the individual first query was submitted; and

tag an individual second query entered by the user as part of the second historical search context with a second seasonal time when the individual second query was submitted,

wherein the first seasonal time and the second seasonal time occur in different weeks.

20. The system of claim 13, wherein the computer-executable instructions further cause the processing unit to:

iteratively train the classifier to recognize additional historical search contexts based on subsequent training data obtained as the user enters subsequent clicks during subsequent user sessions.