Patent US7158966B2 successfully refreshed from Google Patents.
US7158966B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
User intent discovery
Assignee: Microsoft Technology Licensing LLC
•
Filing: 2004-03-09
•
Granted: 2007-01-02
•
Expires: 2024-03-09
Abstract
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.
Inventors
- 👤 Eric D. Brill
- 👤 Harold C. Daume, III
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 18:07
CPC Classifications
G; G01; G01B; G01B5/00; G01B5/24; G01B5/255; G06; G06F; G06F16/00; G06F16/90; G06F16/95; G06F16/953; G06F16/9535; B; B60; B60S; B60S9/00; B60S9/02; B60S9/04; G01B5/0002; G01B5/0007; G06F16/30; G06F16/33; G06F16/332; G06F16/3322; G06F16/3331; G06F16/3332; G06F16/3338; G01B2210/00; G01B2210/10; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
262 words
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 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.
Claim 2
Independent Claim
262 words
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 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.
Claim 3
Dependent Claim
22 words
The system of claim 1 , wherein the previous queries are obtained via reviewing the result set of the user search query.
Claim 4
Dependent Claim
34 words
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.
Claim 5
Dependent Claim
84 words
The system of claim 3 , the maximal marginal relevance scheme employs the algorithm arg min q ′ [ λ 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′.
Claim 6
Dependent Claim
26 words
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.
Claim 7
Dependent Claim
26 words
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.
Claim 8
Dependent Claim
21 words
The system of claim 1 , further comprising a filter component that removes previous queries that include pre-defined strings from consideration.
Claim 9
Dependent Claim
26 words
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.
Claim 10
Dependent Claim
26 words
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.
Claim 11
Dependent Claim
21 words
The system of claim 1 , further comprising a feedback component that facilitates customization of the system according to user preference.
Claim 12
Dependent Claim
45 words
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.
Claim 13
Dependent Claim
24 words
The system of claim 11 , the contextual information comprising one or more of temperature, time of day, location, and day of a week.
Claim 14
Dependent Claim
29 words
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.
Claim 15
Dependent Claim
11 words
The system of claim 13 , the user profile being portable.
Claim 16
Independent Claim
219 words
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 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 engine and D is a set of objects within a data store that is searched over by the search engine.
Claim 17
Independent Claim
219 words
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 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 engine and D is a set of objects within a data store that is searched over by the search engine.
Claim 18
Dependent Claim
34 words
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.
Claim 19
Dependent Claim
85 words
The system of claim 16 , the maximal marginal relevance scheme employs the algorithm argmin arg min q ′ [ λ 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′.
Claim 20
Dependent Claim
20 words
The system of claim 15 , the objects comprising one or more of documents, sounds, videos, images, and web sites.
Claim 21
Dependent Claim
24 words
The system of claim 15 , a user selects one of the previous queries, the selected previous query employed as the user search query.
Claim 22
Dependent Claim
10 words
A cellular phone comprising the system of claim 15 .
Claim 23
Dependent Claim
11 words
A personal digital assistant comprising the system of claim 15 .
Claim 24
Dependent Claim
9 words
The system of claim 15 stored on a client.
Claim 25
Dependent Claim
22 words
The system of claim 15 , the data store being one of the Internet, an intranet, a server, and a hard drive.
Claim 26
Dependent Claim
52 words
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.
Claim 27
Dependent Claim
14 words
The system of claim 24 , the serendipity component being alterable by a user.
Claim 28
Dependent Claim
31 words
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.
Claim 29
Independent Claim
246 words
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 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 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.
Claim 30
Independent Claim
246 words
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 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 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.
Claim 31
Dependent Claim
35 words
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.
Claim 32
Dependent Claim
23 words
The method of claim 27 , further comprising positioning the selected query within a plurality of queries according to the level of relatedness.
Claim 33
Dependent Claim
22 words
The system of claim 27 , further comprising choosing the displayed query and utilizing the displayed query as the user search query.
Claim 34
Dependent Claim
22 words
The method of claim 27 , the data store being one of the Internet, an intranet, a server, and a hard drive.
Claim 35
Independent Claim
201 words
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 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 engine and D is a set of objects within a data store that is searched over by the search engine.
Claim 36
Independent Claim
201 words
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 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 engine and D is a set of objects within a data store that is searched over by the search engine.
Claim 37
Dependent Claim
196 words
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 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 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.
Claim 38
Dependent Claim
196 words
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 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 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.
References Cited (Backward Citations)
US6289353B1
Cited
US6732088B1
Cited
US20020052674A1
Cited
US20030135495A1
Cited
US20030101286A1
Cited
US20050102259A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2010-01-01 | 2010-07-03 | 2011-01-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2014-01-01 | 2014-07-03 | 2015-01-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2018-01-01 | 2018-07-03 | 2019-01-02 | $7700.00 | Window Closed / Lapsed |