User intent discovery

• US 20050203878A1
• Filed: 03/09/2004
• Published: 09/15/2005
• Est. Priority Date: 03/09/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Brill, Eric D., Daume, Harold C. III
• Granted Patent: US 7,158,966 B2
• Time in Patent Office: Days
• 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; and

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.

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 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.

4. The system of claim 3, wherein the distance metrics are determined by utilizing the algorithm

$$

q , q ′



= 1 - 

R ⁡

[ q ] ⋂

R ⁡

[ q ′

] 



R ⁡

[ q ] ⋃

R ⁡

[ q ′

] 

,

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.

5. The system of claim 4, 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.

6. The system of claim 5, the maximal marginal relevance scheme employs the algorithm

$\underset{q^{\prime }}{\mathrm{argmin}}$

⁡

[ λ

⁢



q , q ′



- ( 1 - λ

) ⁢

min q ′

′

⁢



q ′

, q ′

′



] ,

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′

.

7. 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.

8. 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.

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

10. 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.

11. 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.

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

13. 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.

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

15. 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.

16. The system of claim 15, the user profile being portable.

17. 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.

18. The system of claim 17, the level of relatedness based at least in part upon distance metrics between the user search query and the previous queries.

19. The system of claim 18, wherein the distance metrics are determined by utilizing the algorithm

$$

q , q ′



= 1 - 

R ⁡

[ q ] ⋂

R ⁡

[ q ′

] 



R ⁡

[ q ] ⋃

R ⁡

[ q ′

] 

,

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.

20. The system of claim 19, 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.

21. The system of claim 20, the maximal marginal relevance scheme employs the algorithm

$\underset{q^{\prime }}{\mathrm{argmin}}$

⁡

[ λ

⁢



q , q ′



- ( 1 - λ

) ⁢

min q ′

′

⁢



q ′

, q ′

′



] ,

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′

.

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

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

24. A cellular phone comprising the system of claim 17.

25. A personal digital assistant comprising the system of claim 17.

26. The system of claim 17 stored on a client.

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

28. The system of claim 17, 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.

29. The system of claim 28, the serendipity component being alterable by a user.

30. The system of claim 28, 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.

31. 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;

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

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.

32. The method of claim 31, further comprising utilizing distance metrics to calculate the level of relatedness between the result set of the previous query and the user search result set.

33. The method of claim 32, 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.

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

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

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

37. 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.

38. The system of claim 37, wherein the level of relatedness is determined at least in part by comparing a result set associated with the user search query with a result set associated with the previously utilized queries.

39. 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; and

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