Methods and apparatus for retrieving and/or processing retrieved information as a function of a user's estimated knowledge

• US 6,006,218 A
• Filed: 02/28/1997
• Issued: 12/21/1999
• Est. Priority Date: 02/28/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kanazawa, Keiji, Kadie, Carl, Horvitz, Eric, Heckerman, David E., Breese, John S.
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): WALLACE, MICHAEL J
• Application Number:
  US08/807,566
• Time in Patent Office: 1,026 Days
• Field of Search: 707/3, 707/4, 707/5, 707/6, 707/10, 707/2
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9536 Search customisation based on social or collaborative filtering
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Information retrieval methods and apparatus which involve: 1) the generation of estimates regarding the probability that items included in search results are already known to the user and 2) the use of such knowledge probability estimates to influence the ranking of search results, are described. By discounting the ranking, or adjusting ranking values generated by a known search engine as a function of the knowledge probability estimates, the present invention reduces or eliminates the risk of locating known information near the top of a list of search results. This is advantageous since known information is generally of little interest to a user. In various embodiments the popularity of an item is used to estimate the probability that the item is already known to a user. In addition, in various embodiments one or more user controllable parameters are used in the generation of the knowledge probability estimates and/or the ranking of the search results to give the user an opportunity to have the ranking of the search results accurately reflect the user'"'"'s knowledge. The present invention is particularly well suited to collaborative filtering based search systems. This is because collaborative filters make recommendations to a user based on historical information relating to, e.g., the popularity of items being considered for recommendation. This same popularity information can be used to estimate a users knowledge of a database item. Such items may include television shows, music, Internet sites, etc.

Claims

1. A method of retrieving information for a user, the method, comprising the steps of:

generating a set of search results including a plurality of entries, at least some of said entries not being known to the user; and

arranging the set of search results for presentation to the user from top to bottom, using estimates of the probability that the entries are known to the user, the step of arranging being performed so that entries having a higher probability of being known to the user are less likely to be placed at the top of the arranged set of search results then entries which have a lower probability of being known to the user.

2. The method of claim 1, further comprising the step of:

generating, for each entry in the set of search results, an estimate of the probability that the particular entry, for which the estimate is being generated, is known to the user.

3. The method of claim 2, wherein the step of generating an estimate that the particular entry is known to the user is performed as a function of a user controlled parameter indicative of the knowledge level of the user.

4. The method of claim 2, wherein the step of generating an estimate that the particular entry is known to the user is performed as a function of popularity information relating the particular entry.

5. The method of claim 4, wherein the step of generating an estimate that the particular entry is known to the user is also performed as a function of a user controlled parameter indicative of the knowledge level of the user.

6. The method of claim 2, wherein the step of generating an estimate that the particular entry is known to the user is performed as a function of the salience of information associated with each particular entry.

7. The method of claim 2, wherein the step of generating an estimate that the particular entry is known to the user is performed as a function of user demographic information.

8. The method of claim 2, wherein the step of generating an estimate that the particular entry is known to the user is performed as a function of the amount of time an item has been accessible to the public.

9. The method of claim 2, wherein the step of generating an estimate that the particular entry is known to the user is performed as a function of an information content associated with each particular entry.

10. The method of claim 2, wherein the step of generating an estimate that a particular entry is known to the user is performed as a function of the particular entry'"'"'s rank in a popularity list.

11. The method of claim 1,

wherein the step of generating a set of search results includes the step of:

ranking the entries included in the set of search results by generating for, and associating with, each one of the entries a rank indicator, pRank, having a numerical value indicating the entry'"'"'s rank in the set of search results; and

wherein the step of arranging the set of search results includes the step of;

altering the value of a plurality of the rank indicators as a function of the estimate that the entries in the set of search results is known to the user.

12. The method of claim 11, wherein the step of estimating the probability that the entries in the set of search results are known to the user includes the step of:

generating, for each entry in the set of search results, an estimate represented as a value, pKnow, that the particular entry for which the estimate is being generated, is known to the user.

13. The method of claim 1,

wherein the step of generating the set of search results further includes the step of:

generating, for each individual entry in the set of search results, a score indicative of the relevance of the individual entry;

the method further comprising the steps of;

generating a knowledge probability estimate, corresponding to each individual entry included in the set of search results, the knowledge probability estimate representing an estimate of the probability that information included in the corresponding entry is not known to the user; and

ranking the entries, in the set of search results, as a function of new scores generated for the entries in the set of search results, a new score being generated for each entry as the product of the entry'"'"'s previously generated knowledge probability estimate and score.

14. The method of claim 13, wherein the knowledge probability estimate corresponding to each individual entry is generated as a function of an estimate that the user knows about the information included in the corresponding entry.

15. The method of claim 1,

wherein the step of generating the set of search results further includes the step of:

generating, for each individual entry in the set of search results, a score indicative of the relevance of the individual entry;

the method further comprising the steps of;

generating a knowledge probability estimate, corresponding to each individual entry included in the set of search results, the knowledge probability estimate representing a measure of the likelihood that information including in the corresponding entry is not known to the user; and

ranking the entries, in the set of search results, as a function of new scores generated for the entries in the set of search results, a new score being generated for each entry as the product of the entry'"'"'s previously generated knowledge probability estimate and score.

16. The method of claim 15, wherein the knowledge probability estimate corresponding to each individual entry is generated as a function of an estimate that the user knows about the information included in the corresponding entry.

17. The method of claim 1, further comprising the steps of:

generating value estimates representing estimates of the value to the user of reviewing individual items included in the set of search results;

generating knowledge probability estimates representing estimates of the probability that the user does not know about individual items in the set of search results; and

wherein the step of arranging the set of search results is performed as a function of the generated value estimates and generated knowledge probability estimates.

18. The method of claim 17, further comprising the step of:

generating cost estimates representing estimates of the cost to the user associated with reviewing an item in the set of search results.

19. The method of claim 18, wherein the step of arranging the set of search results is also performed as a function of the generated cost estimates.

20. The method of claim 19, further comprising the step of:

calculating a comprehensive value representing an estimate of the value of reviewing an entire set of search results as a function of the estimated value of reviewing individual items included in the set of search results.

21. The method of claim 20, wherein the comprehensive value is computed as a function of the sum of the estimated value of reviewing individual items included in the set of search results.

22. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 1.

23. The method of claim 1, wherein the step of arranging the set of search results includes the step of:

assigning a lower rank to a first entry having a higher probability of being known to the user than to a second entry having a lower probability of being known to the user.

24. The method of claim 1, wherein the entries are not known to have been reviewed by the user, the method further comprising the step of:

eliminating from the set of search results the entry having the highest estimated probability of being known to the user.

25. The method of claim 1, wherein the step of arranging the set of search results includes the step of generating scores used for ranking the entries, the score being generated as a product of a plurality of factors, one factor being a function of the estimated probability of an entry being known to the user, said factor being smaller for entries having a higher probability of being known to a user than for entries having a lower probability of being known to a user.

26. An information retrieval system comprising:

a user input device for receiving database search requests from a user;

a database including a plurality of entries;

means for generating knowledge probability estimates representing the probability that individual database entries are known to the user; and

a search engine coupled to the user input device, the database, and the means for generating knowledge probability estimates, the search engine including means for ranking the search results as a function of the generated knowledge probability estimates, a database entry included in the search results having a first probability of being known to the user being weighted in favor of receiving a higher ranking than database entrees having a probability of being known to the user which is greater than the first probability;

eliminating from the set of search results the entry having the highest estimated probability of being known to the user.

27. A processing apparatus for processing ranked search results, comprising:

a knowledge probability estimator for estimating the probability that one or more entries included in the database being searched are known to the user; and

a search result adjuster coupled to the knowledge probability estimator for re-ordering the search results as a function of the estimated probability that one or more entries included in the search results are known to the user, the search result adjuster including means for re-ranking the search results to reflect a diminution in the relative rank of search results which are estimated to already be known to the user.

28. A method of retrieving information for a user, the method, comprising the steps of:

generating a set of search results including a plurality of entries, at least some of said entries not being known to the user, the step of generating the set of search results including the step of ranking the entries in the set of search results; and

arranging the set of search results for presentation to the user from top to bottom, using estimates of the probability that the entries are known to the user, the step of arranging the set of search results, including the step of;

adjusting the ranking of the entries in the set of search results, the rank of each particular entry being adjusted as a function of the ranking of the particular entry and the estimated probability that the particular entry is known to the user.

29. The method of claim 28,

wherein the step of generating a set of search results includes the step of:

performing a collaborative filtering operation using stored historical information and information about the preferences and attributes of the user.

30. The method of claim 29,

wherein the step of estimating the probability that the entries in the set of search results are known to the user includes the use of at least a portion of the stored historical information.

31. The method of claim 28, further comprising the step of:

monitoring the user'"'"'s actions for a period of time; and

wherein the step of generating a set of search results further includes the step of conduction a search as a function of the user'"'"'s monitored actions.

32. The method of claim 28, wherein the step of generating a set of search results includes:

the step of conducting a search of a database in response to an information retrieval request from the user.

33. The method of claim 32, wherein the step of generating, for each entry in the set of search results, an estimate that the particular entry for which the estimate is being generated is known to the user, is performed prior to the step of generating the set of search results by generating an estimate for each entry in the database being searched.

34. The method of claim 28, wherein the step of generating a set of search results further comprises the step of:

accessing a database including information on Internet sites.

35. The method of claim 28, wherein the step of generating a set of search results further comprises the step of:

accessing a database including information on television shows.

36. The method of claim 28, wherein the step of generating a set of search results further comprises the step of:

accessing a database including information on music.

37. A processing apparatus for re-ordering a set of information items ordered for presentation to a user, the set of information items including at least one information item not known to the user, the apparatus comprising:

a knowledge probability estimator for estimating the probability that one or more entries included in the set of information items are known to the user; and

an order adjusting device for re-ordering the search results as a function of the estimated probability that one or more entries included in the database being searched are known to the user to decrease the probability that information items already known to the user will be located at the top of the ordered set of information items.

38. The processing apparatus of claim 37, wherein the knowledge probability estimator includes means for receiving a plurality of factors used for estimating said probability.

39. The processing apparatus of claim 38, wherein one of said plurality of factors is the age of entries included in the search results and another of said plurality of factors is the popularity of entries included in the search results.

40. An information retrieval system for searching a database including a plurality of entries, the system comprising:

a search engine coupled to the database;

a knowledge probability estimator coupled to the search engine for estimating the probability that entries in the database are known to a user of the information retrieval system; and

a retrieval result adjusting module coupled to the search engine for receiving therefrom search results including database entries and for ranking the received search results as a function of the estimated probability that the entries included in the search results are known to the user, the retrieval result adjusting module favoring for a higher ranking for database entries which are less likely to be known to the user than entries which are more likely to be known to a user.

41. The apparatus of claim 40, further comprising:

means for presenting the ranked search results to the user.

42. The apparatus of claim 41, further comprising:

a user input device coupled to the knowledge probability estimator for supplying thereto user input indicative of the knowledge level of the user.

43. The apparatus of claim 42,

wherein the search engine is a collaborative filter;

wherein the database includes information on the popularity of entries in the database; and

the apparatus further includes means for supplying the popularity information included in the database to both the knowledge probability estimator and the collaborative filter.

44. The apparatus of claim 43, further comprising:

a user database coupled to the collaborative filter and to the knowledge probability estimator, the user database including information on user attributes and preferences.

45. The apparatus of claim 44, further comprising:

means for coupling the database to the search engine via the Internet.

46. The apparatus of claim 40,

wherein the search engine is of a type which ranks the search results according to a first preselected ranking scheme;

and

wherein the ranking performed by the retrieval result adjusting module results in modifications to the ranking of the search results previously ranked according to the first preselected ranking scheme.

47. The apparatus of claim 46, wherein the search engine is a collaborative filter.