Forming intent-based clusters and employing same by search

• US 7,657,519 B2
• Filed: 09/30/2004
• Issued: 02/02/2010
• Est. Priority Date: 09/30/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: White, Thomas D., Malolepsy, Paul M., Marsman, Jennifer J., Mydland, Mark B., Anderson, Blake E., Karnawat, Kuldeep, Finger, James C.
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): Le; Hung D
• Application Number:
  US10/955,593
• Publication Number:
  US 20060074902A1
• Time in Patent Office: 1,951 Days
• Field of Search: 707/5, 707/2, 707/6, 707/3, 707/9, 707/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/337 Profile generation, learning or modification
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method is provided for analyzing a plurality of search sessions to identify intent-based clusters therein. Each session comprises at least one received query from a user and a corresponding set of returned search results, and each set of search results includes or refers to at least one piece of content. Each cluster represents a group of similar search sessions that are perceived as representing a common purpose and that can be mapped to a common set of search results. In the method, for each search session, each received query thereof, the corresponding set of search results, and whether any particular piece of content of the search results was acceptable to the user as responsive to the corresponding search session are identified. Thereafter, search sessions are grouped into clusters.

Claims

1. A method for analyzing a plurality of search sessions to identify intent-based clusters therein, each session comprising at least one received query from a user and a corresponding set of returned search results, each set of search results including or referring to at least one piece of content, each cluster representing a group of similar search sessions that are perceived as representing a common intent of a plurality of different users and that can be mapped to a common set of search results, the method comprising:

identifying for each search session each received query thereof, the corresponding set of search results, and whether any particular piece of content of the search results was acceptable to the user as responsive to the corresponding search session; and

grouping search sessions into clusters based on the commonality of judgments of a plurality of different users about a search result that is common to the user'"'"'s respective search sessions, wherein each of said clusters includes search queries and search results, such grouping comprising;

constructing a table with a plurality of entries therein, each entry representing a unique pair of sessions such that each session is paired with every other session a single time in the table;

judging, for each entry of the table, a strength of commonality of the pair of sessions thereof;

reordering the entries in the table according to decreasing strength; and

reviewing each entry in the table as reordered to decide based on the judged strength thereof whether to assign each session thereof to an intent-based cluster.

2. The method of claim 1 wherein a user'"'"'s judgment about a search result is determined by identifying any particular piece of content of the search results that was acceptable to the user based on factors including whether the user accessed the piece of content and how much time the user spent reviewing such piece of content.

3. The method of claim 1, wherein in addition to judging the commonality of judgments about a search result, the method further comprises judging the commonality of text in queries submitted in the different search sessions.

4. The method of claim 3 wherein the strength of commonality of the pair of sessions is based at least in part on whether the pair of sessions had the same or a similar query.

5. The method of claim 1 wherein the strength of commonality of the pair of sessions is based at least in part on whether the pair of sessions resulted in the same or similar content which was found to evoke a similar judgment about the results in both sessions.

6. The method of claim 1 comprising reviewing each entry in the table as reordered to decide whether to assign each session to an intent-based cluster by deciding for each entry in the table whether the sessions thereof are found to have a minimum commonality by having a judged strength above a defined threshold, and if so assigning both of such sessions of the entry to a cluster according to the following rules:

if one of the sessions is already assigned to a cluster, then the other session is assigned to the same cluster;

if neither session is already in a cluster, then such sessions are assigned to a new cluster; and

if both sessions are already in separate clusters, then do nothing.

7. The method of claim 1 further comprising mapping each cluster to a common set of search results that is believed to satisfy the common purpose of such cluster so that all queries with the same common purpose map correctly based on such cluster.

8. A computer-readable medium having stored thereon computer-executable instructions for performing a method of analyzing a plurality of search sessions to identify intent-based clusters therein, each session comprising at least one received query from a user and a corresponding set of returned search results, each set of search results including or referring to at least one piece of content, each cluster representing a group of similar search sessions that are perceived as representing a common intent of a plurality of different users and that can be mapped to a common set of search results, the method comprising:

identifying for each search session each received query thereof, the corresponding set of search results, and whether any particular piece of content of the search results was acceptable to the user as responsive to the corresponding search session; and

grouping search sessions into clusters based on the commonality of judgments of a plurality of different users about a search result that is common to the user'"'"'s respective search sessions, wherein each of said clusters includes search queries and search results, such grouping comprising;

constructing a table with a plurality of entries therein, each entry representing a unique pair of sessions such that each session is paired with every other session a single time in the table;

judging, for each entry of the table, a strength of commonality of the pair of sessions thereof;

reordering the entries in the table according to decreasing strength; and

reviewing each entry in the table as reordered to decide based on the judged strength thereof whether to assign each session thereof to an intent-based cluster.

9. The medium of claim 8 wherein a user'"'"'s judgment about a search result is determined by identifying any particular piece of content of the search results that was acceptable to the user based on factors including whether the user accessed the piece of content and how much time the user spent reviewing such piece of content.

10. The medium of claim 8 wherein in addition to judging the commonality of judgments about a search result, the method further comprises judging the commonality of text in queries submitted in the different search sessions.

11. The medium of claim 8 wherein the strength of commonality of the pair of sessions is based at least in part on whether the pair of sessions resulted in the same or similar content which was found to evoke a similar judgment in both sessions.

12. The medium of claim 8 wherein the strength of commonality of the pair of sessions is based at least in part on whether the pair of sessions had the same or a similar query.

13. The medium of claim 8 wherein the method comprises reviewing each entry in the table as reordered to decide whether to assign each session to an intent-based cluster by deciding for each entry in the table whether the sessions thereof are found to have a minimum commonality by having a judged strength above a defined threshold, and if so assigning both of such sessions of the entry to a cluster according to the following rules:

if one of the sessions is already assigned to a cluster, then the other session is assigned to the same cluster;

if neither session is already in a cluster, then such sessions are assigned to a new cluster; and

if both sessions are already in separate clusters, then do nothing.

14. The medium of claim 8 wherein the method further comprises mapping each cluster to a common set of search results that is believed to satisfy the common purpose of such cluster so that all queries with the same common purpose map correctly based on such cluster.

15. A method for responding to a received query based on a mapping of intent-based clusters of prior search sessions to content, each search session comprising at least one received query from a user and a corresponding set of returned search results, each set of search results including or referring to at least one piece of content, the method comprising:

analyzing the received query by comparing same to prior queries of sessions of intent-based clusters to determine a prior query that the received query matches, wherein the intent-based clusters are created by;

grouping search sessions into clusters based on the commonality of judgments of a plurality of different users about a search result that is common to the user'"'"'s respective search sessions, wherein each of said clusters includes search queries and search results, such grouping comprising;

constructing a table with a plurality of entries therein, each entry representing a unique pair of sessions such that each session is paired with every other session a single time in the table;

judging, for each entry of the table, a strength of commonality of the pair of sessions thereof;

reordering the entries in the table according to decreasing strength; and

reviewing each entry in the table as reordered to decide based on the judged strength thereof whether to assign each session thereof to an intent-based cluster;

identifying the session of the matched prior query;

identifying the intent-based cluster of the identified session identifying the mapped-to content of the identified intent-based cluster; and

employing the mapped-to content in returning a response to the received query.