User intent discovery

• US 7,158,966 B2
• Filed: 03/09/2004
• Issued: 01/02/2007
• Est. Priority Date: 03/09/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Brill, Eric D., Daume, Harold C. III
• Primary Examiner(s): Kindred; Alford W.
• Application Number:
  US10/796,378
• Publication Number:
  US 20050203878A1
• Time in Patent Office: 1,029 Days
• Field of Search: 707 1- 3, 707/100, 707/103, 717/108
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

a system 100 that facilitates determining a user'"'"'s intent given a user search query comprises a search engine that is employed to search over a collection of objects within a data store to retrieve a user search result set. The objects within the result set are associated with queries that were previously utilized to locate such objects. A level of relatedness between the previous queries and the user search query is determined, and previous queries that are associated with a result set that is novel and related to the user search result set are returned to the user.

Claims

1. A system that facilitates determining an intent of a user, comprising:

a search component that identifies a result set for a user search query;

a data store that maintains objects, the data store correlates the objects with queries that were previously employed to retrieve the objects;

a user intent discovery component that determines a set of potential search areas based at least in part upon the result set of the user search query and results of previous queries;

a query relation calculator that determines a level of relatedness between the user search query and the previous queries, the query relation calculator selects previous queries to display to the user based at least in part upon the calculated level of relatedness;

wherein a level of relation between the previous queries and the user search query is obtained at least in part by determining distance metrics between the previous queries and the user search query; and

wherein the distance metrics are determined by utilizing the algorithm

$<br><br><br><br>q,q^{\mathrm{\prime <br><br>}}<br><br><br><br>=1-\frac{<br><br>R<br><br>\left[q\right]\bigcap <br><br>R<br><br>\left[q^{\mathrm{\prime <br><br>}}\right]<br><br>}{<br><br>R<br><br>\left[q\right]\bigcup <br><br>R<br><br>\left[q^{\mathrm{\prime <br><br>}}\right]<br><br>}$

 

where ∥

q,q′

∥

is a distance metric between the user search query q and one or more previous queries q′

, and R is a binary relation on Q×

D, wherein Q is a set of queries previously employed by the search component and D is a set of objects within a data store that is searched over by the search component.

2. The system of claim 1, wherein the previous queries are obtained via reviewing the result set of the user search query.

3. The system of claim 1, wherein the level of relation between the previous queries and the user search query is obtained at least in part by utilizing a modified maximal marginal relevance scheme.

4. The system of claim 3, the maximal marginal relevance scheme employs the algorithm

$\underset{q^{\mathrm{\prime <br><br>}}}{\arg \; <li></li><br><br>\min }<br><br>\left[\mathrm{\lambda <br><br>}<br><br><br><br><br><br>q,q^{\mathrm{\prime <br><br>}}<br><br><br><br>-\left(1-\mathrm{\lambda <br><br>}\right)<br><br>\underset{q^{\mathrm{″<br><br>}}}{\min }<br><br><br><br><br><br>q^{\mathrm{\prime <br><br>}},q^{\mathrm{″<br><br>}}<br><br><br><br>\right],$

where λ

is an interpolation factor that is established a priori, and q″

represents one or more previous queries that have already been considered prior to the consideration of q′

.

5. The system of claim 1, further comprising a filter component that limits a number of objects within the result set of the user search query.

6. The system of claim 1, further comprising a filter component that removes previous queries that have fewer words than the user search query from consideration.

7. The system of claim 1, further comprising a filter component that removes previous queries that include pre-defined strings from consideration.

8. The system of claim 1, further comprising a filter component that removes previous queries that are lexically similar to the user search query from consideration.

9. The system of claim 1, further comprising a filter component that removes previous queries that comprise characters that are not printable ASCII characters from consideration.

10. The system of claim 1, further comprising a feedback component that facilitates customization of the system according to user preference.

11. The system of claim 1, further comprising an artificial intelligence component that makes inferences with respect to at least one of selection and arrangement of the potential search areas according to one or more of user state, user history, user context, and contextual information.

12. The system of claim 11, the contextual information comprising one or more of temperature, time of day, location, and day of a week.

13. The system of claim 1 further comprising a user profile, the user profile comprising information relating to at least one of selection and arrangement of the potential search areas.

14. The system of claim 13, the user profile being portable.

15. A system that facilitates determining user intent, comprising:

a search engine that receives a user search query, the search engine searches over objects within a data store according to the user search query, the objects being associated with queries previously employed to locate the objects; and

a query relation calculator that determines a level of relatedness between the user search query and the previous queries, the query relation calculator selects previous queries to display to the user based at least in part upon the calculated level of relatedness;

wherein the level of relatedness is based at least in part upon distance metrics between the user search query and the previous queries; and

wherein the distance metrics are determined by utilizing the algorithm

$<br><br>q,q^{\mathrm{\prime <br><br>}}<br><br>=1-\frac{<br><br>R<br><br>\left[q\right]\bigcap <br><br>R<br><br>\left[q^{\mathrm{\prime <br><br>}}\right]<br><br>}{<br><br>R<br><br>\left[q\right]\bigcup <br><br>R<br><br>\left[q^{\mathrm{\prime <br><br>}}\right]<br><br>},$

 

where ∥

q,q′

∥

is a distance metric between the user search query q and one or more previous queries q′

, and R is a binary relation on Q×

D, wherein Q is a set of queries previously employed by the search engine and D is a set of objects within a data store that is searched over by the search engine.

16. The system of claim 15, wherein the level of relatedness between the previous queries and the user search query is obtained at least in part by utilizing a modified maximal marginal relevance scheme.

17. The system of claim 16, the maximal marginal relevance scheme employs the algorithm argmin

$\underset{q^{\mathrm{\prime <br><br>}}}{\arg \; <li></li><br><br>\min }<br><br>\left[\mathrm{\lambda <br><br>}<br><br><br><br><br><br>q,q^{\mathrm{\prime <br><br>}}<br><br><br><br>-\left(1-\mathrm{\lambda <br><br>}\right)<br><br>\underset{q^{\mathrm{″<br><br>}}}{\min }<br><br><br><br><br><br>q^{\mathrm{\prime <br><br>}},q^{\mathrm{″<br><br>}}<br><br><br><br>\right],$

where λ

is an interpolation factor that is established a priori, and q″

represents one or more previous queries that have already been considered prior to the consideration of q′

.

18. The system of claim 15, the objects comprising one or more of documents, sounds, videos, images, and web sites.

19. The system of claim 15, a user selects one of the previous queries, the selected previous query employed as the user search query.

20. A cellular phone comprising the system of claim 15.

21. A personal digital assistant comprising the system of claim 15.

22. The system of claim 15 stored on a client.

23. The system of claim 15, the data store being one of the Internet, an intranet, a server, and a hard drive.

24. The system of claim 15, further comprising a serendipity component employed to select an amount of overlap required between a return set of the user search query and return sets of the previous queries in connection with determining the level of relatedness between the user search query and the previous queries.

25. The system of claim 24, the serendipity component being alterable by a user.

26. The system of claim 24, the serendipity component being automatically adjusted based at least in part upon one or more of user state, user identity, user context, and user history.

27. A method for assisting a user search over a plurality of objects, comprising:

receiving a user search query;

searching a data store for objects according to the user search query to create a user search result set, the objects being associated with queries previously employed to locate the objects;

reviewing the previously employed queries to locate one or more objects within the user search result set;

determining a level of relatedness between the user search query and the previously employed queries, wherein the level of relatedness is based at least in part upon distance metrics between the user search query and the previously employed queries, and wherein the distance metrics are determined by utilizing the algorithm

$<br><br>q,q^{\mathrm{\prime <br><br>}}<br><br>=1-\frac{<br><br>R<br><br>\left[q\right]\bigcap <br><br>R<br><br>\left[q^{\mathrm{\prime <br><br>}}\right]<br><br>}{<br><br>R<br><br>\left[q\right]\bigcup <br><br>R<br><br>\left[q^{\mathrm{\prime <br><br>}}\right]<br><br>},$

 

where ∥

q,q′

∥

is a distance metric between the user search query q and one or more previous queries q′

, and R is a binary relation on Q×

D, wherein Q is a set of queries previously employed by the search engine and D is a set of objects within a data store that is searched over by the search engine;

selecting a query that was previously employed based upon a calculated level of relatedness between a result set of the previous query and the user search result set; and

displaying the retrieved query.

28. The method of claim 27, further comprising utilizing a modified maximal marginal relevance scheme to calculate the level of relatedness between the result set of the previous query and the user search result set.

29. The method of claim 27, further comprising positioning the selected query within a plurality of queries according to the level of relatedness.

30. The system of claim 27, further comprising choosing the displayed query and utilizing the displayed query as the user search query.

31. The method of claim 27, the data store being one of the Internet, an intranet, a server, and a hard drive.

32. A system that assists a user in connection with searching for objects, comprising:

means for associating objects with queries previously utilized to locate such objects;

means for searching over the objects given a user search query;

means for determining a level of relatedness between the previously utilized queries and the user search query; and

means for displaying previously utilized queries according to the determined level or relatedness, wherein the level of relatedness is determined based at least in part upon distance metrics between the user search query and the previously employed queries, and wherein the distance metrics are determined by utilizing the algorithm

$<br><br><br><br>q,q^{\mathrm{\prime <br><br>}}<br><br><br><br>=1-\frac{<br><br>R<br><br>\left[q\right]\bigcap <br><br>R<br><br>\left[q^{\mathrm{\prime <br><br>}}\right]<br><br>}{<br><br>R<br><br>\left[q\right]\bigcup <br><br>R<br><br>\left[q^{\mathrm{\prime <br><br>}}\right]<br><br>}$

 

where ∥

q,q′

∥

is a distance metric between the user search query q and one or more previous queries q′

, and R is a binary relation on Q×

D, wherein Q is a set of queries previously employed by the search engine and D is a set of objects within a data store that is searched over by the search engine.

33. A computer readable medium having computer executable instructions stored thereon to:

search over a plurality of objects given a user search query, the objects associated with queries previously employed to locate such objects;

calculate a level of relatedness between the user search query and the previously employed queries, wherein the level of relatedness is determined based at least in part upon distance metrics between the user search query and the previously employed queries, and wherein the distance metrics are determined by utilizing the algorithm

$<br><br><br><br>q,q^{\mathrm{\prime <br><br>}}<br><br><br><br>=1-\frac{<br><br>R<br><br>\left[q\right]\bigcap <br><br>R<br><br>\left[q^{\mathrm{\prime <br><br>}}\right]<br><br>}{<br><br>R<br><br>\left[q\right]\bigcup <br><br>R<br><br>\left[q^{\mathrm{\prime <br><br>}}\right]<br><br>}$

 

where ∥

q,q′

∥

is a distance metric between the user search query q and one or more previous queries q′

, and R is a binary relation on Q×

D, wherein Q is a set of queries previously employed by the search engine and D is a set of objects within a data store that is searched over by the search engine; and

display one or more previous queries according to the calculated level of relatedness.