Technique for prefetching a web page of potential future interest in lieu of continuing a current information download

• US 6,067,565 A
• Filed: 01/15/1998
• Issued: 05/23/2000
• Est. Priority Date: 01/15/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric
• Primary Examiner(s): COULTER, KENNETH R
• Application Number:
  US09/007,894
• Time in Patent Office: 859 Days
• Field of Search: 709/218, 709/223, 709/234, 395/200.48
• US Class Current: 709/218
• CPC Class Codes: G06F 16/95 Retrieval from the web
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A technique that, through continual computation, harnesses available computer resources during periods of low processing activity and low network activity, such as idle time, for prefetching, e.g., web pages, or pre-selected portions thereof, into local cache of a client computer. This technique utilizes, e.g., a probabilistic user model, which specifies, at any one time, those pages or portions of pages that are likely to be prefetched given, e.g., a web page currently being rendered to a user; these pages being those which promise to provide the largest benefit (expected utility) to the user. Advantageously, this technique prematurely terminates or retards a current information download for a user in favor of prefetching a web page of future interest to that user whenever the latter page exhibits greater current incremental benefit to that user, in terms of a discounted expected rate of refinement in value with time for the future page, than a current incremental benefit being obtained for that user by continuing the current download.

Claims

1. In a client computer system that, in response to user interaction with the system, requests items of information, as desired by a user, from a server, a method of obtaining the items of information comprising the steps of:

(a) downloading, in response to a request from the user, a first item of information from the server so as to define a current download and rendering portions of the first item of information as it is being downloaded; and

(b) while the current download progresses;

determining, in response to a predefined aspect of the first item and a predefined user model, at least one second item of information which the user is likely to request next from the server;

ascertaining incremental benefit to the user of continuing the current download and expected incremental benefit to the user of the second item of information; and

in the event the expected incremental benefit of the second item exceeds the incremental benefit of continuing the current download, deallocating computational or network resources from continuing the current download and allocating the resources towards collectively prefetching and storing the second item of information so as to then obtain the second item for future access in the event the user subsequently requests the second item.

2. The method in claim 1 wherein the allocating step comprises the step of terminating the current download prior to its completion or retarding a rate at which the current download occurs.

3. The method in claim 2 further comprising repeating steps (b) at an onset of each one of a plurality of successively occurring time intervals.

4. The method in claim 3 wherein the server comprises a web server accessible over a networked connection, wherein the networked connection comprises either an Internet connection or an intra-net connection.

5. The method in claim 4 wherein each of the first and second items comprises a corresponding web page or predefined page component thereof, and the predefined aspect is an address associated with the first quantity of information.

6. The method in claim 5 further comprising the steps of, at the onset of said each one time interval:

determining a first rate of refinement in value with time for the first item as the incremental benefit of the first item;

determining a discounted flux-product for the second item as the expected incremental benefit of the second item;

comparing, the first rate of refinement in value with the discounted flux-product for the second item; and

if the discounted flux-product exceeds the first rate of refinement in value;

terminating or retarding the current download; and

prefetching and storing the second item.

7. The method in claim 6 further comprising the steps of:

producing, in response to a first utility measure associated with the first item, the first rate of refinement with time;

producing, in response to a second utility measure associated with the second item, a second rate of refinement in value with time for the second item; and

generating the discounted flux-product as a product of the second rate of refinement, a transition probability associated with the second item and a discount factor.

8. The method in claim 7 wherein the step of producing the first rate of refinement comprises the step of generating the first rate of refinement as a predetermined function of a speed at which the first item is downloaded from the server, a size of the first item and a utility measure associated with the first item.

9. The method in claim 7 wherein the first and second utility measures are each a corresponding stored value, a predefined stored function or a predefined stored look-up table.

10. The method in claim 7 wherein the discount factor, d, is a number in the range 0<

d≦

1.

11. The method in claim 7 wherein the user model provides the transition probability for the second item in response to user activity, a user profile, structure or content of text or graphics associated with the first item.

12. The method in claim 11 wherein the user model is further responsive to statistical data obtained on the client computer or the server.

13. The method in claim 12 wherein the user model incorporates statistically analyzed log usage data.

14. The method in claim 13 wherein the user model further comprises a decision tree derived from a Bayesian network, a Bayesian model or a Hidden Markov model.

15. The method in claim 13 wherein the user model resides on the server, further comprising the step of providing, through the user model and in response to statistically analyzed server-based log data and the first item or a succession of items, including the first item, downloaded from the server to the client computer, the transition probability for the second item.

16. The method in claim 15 wherein the probability providing step comprises the step of determining the transition probability in response to a profile stored on either the client computer or the server.

17. The method in claim 16 wherein the transition probability determining step of ascertaining the transition probability in response to user activity.

18. The method in claim 13 further comprising the step of generating, through the user model and in response to user interactivity with the client computer, the transition probability for the second item.

19. The method in claim 13 wherein the interactivity comprises measurements of user scroll, user dwell, or position or user movement of a mouse pointer on the first item as rendered.

20. The method in claim 15 further comprising the step of generating, through the user model and in response to a pre-defined attribute of the first item, the transition probability for the second item.

21. The method in claim 20 wherein the predefined attribute comprises class, structure or layout of the first page, or content or context of text, graphics or hypertext links on the first item.

22. The method in claim 15 further comprising the step of generating, through the user model and in response to results returned by a search engine , the transition probability for the second item.

23. The method in claim 22 wherein the results comprise a similarity measure, a keyword in either a returned item from the search engine or a predefined field associated therewith, or content of the returned item.

24. The method in claim 15 further comprising the step of generating, through the user model and in response to content in the first item or within a predefined field associated with the first item, the transition probability for the second item.

25. The method in claim 24 wherein the predefined field comprises a description, summary or tag field.

26. The method in claim 15 further comprising the step of generating, through the user model and in response to collaborative filtering of the first item, the transition probability for the second item.

27. The method in claim 15 further comprising the step of generating, through the user model and in response to characteristics of user eye movement, the transition probability for the second item.

28. The method in claim 27 wherein the user eye movement characteristics comprise real-time measurements of actual eye movement of an individual user or a statistical model of user gaze patterns across a plurality of users.

29. A computer readable medium having computer executable instructions stored there in for performing the steps of claim 1.

30. Apparatus for a client computer system that, in response to user interaction with the system, requests items of information, as desired by a user, from a server, the apparatus comprising:

a processor;

a memory having computer executable instructions stored therein;

wherein, in response to the stored instructions, the processor;

(a) downloads, in response to a request from the user, a first item of information from the server so as to define a current download and rendering portions of the first item of information as it is being downloaded; and

(b) while the current download progresses;

determines, in response to a predefined aspect of the first item and a predefined user model, at least one second item of information which the user is likely to request next from the server;

ascertains incremental benefit to the user of continuing the current download and expected incremental benefit to the user of the second item of information; and

in the event the expected incremental benefit of the second item exceeds the incremental benefit of continuing the current download, deallocates computational or network resources from continuing the current download and allocates the resources towards collectively prefetching and storing the second item of information so as to then obtain the second item for future access in the event the user subsequently requests the second item.

31. The apparatus in claim 30 wherein the processor, in response to the stored instructions, terminates the current download prior to its completion or retards a rate at which the current download occurs.

32. The apparatus in claim 31 wherein the processor, in response to the stored instructions, repeats operations (b) at an onset of each one of a plurality of successively occurring time intervals.

33. The apparatus in claim 32 wherein the server comprises a web server accessible over a networked connection, wherein the networked connection comprises either an Internet connection or an intra-net connection.

34. The apparatus in claim 33 wherein each of the first and second items comprises a corresponding web page or predefined page component thereof, and the predefined aspect is an address associated with the first quantity of information.

35. The apparatus in claim 34 wherein the processor, in response to the stored instructions and at the onset of said each one time interval:

determines a first rate of refinement in value with time for the first item as the incremental benefit of the first item;

determines a discounted flux-product for the second item as the expected incremental benefit of the second item;

compares, the first rate of refinement in value with the discounted flux-product for the second item; and

if the discounted flux-product exceeds the first rate of refinement in value;

terminates or retarding the current download; and

prefetches and stores the second item.

36. The apparatus in claim 35 wherein the processor, in response to the stored instructions:

produces, in response to a first utility measure associated with the first item, the first rate of refinement with time;

produces, in response to a second utility measure associated with the second item, a second rate of refinement in value with time for the second item; and

generates the discounted flux-product as a product of the second rate of refinement, a transition probability associated with the second item and a discount factor.

37. The apparatus in claim 36 wherein the processor, in response to the stored instructions, generates the first rate of refinement as a predetermined function of a speed at which the first item is downloaded from the server, a size of the first item and a utility measure associated with the first item.

38. The apparatus in claim 36 wherein the first and second utility measures are each a corresponding stored value, a predefined stored function or a predefined stored look-up table.

39. The apparatus in claim 36 wherein the discount factor, d, is a number in the range 0<

d≦

1.

40. The apparatus in claim 36 wherein the user model provides the transition probability for the second item in response to user activity, a user profile, structure or content of text or graphics associated with the first item.

41. The apparatus in claim 40 wherein the user model is further responsive to statistical data obtained on the client computer or the server.

42. The apparatus in claim 41 wherein the user model incorporates statistically analyzed log usage data.

43. The apparatus in claim 42 wherein the user model further comprises a decision tree derived from a Bayesian network, a Bayesian model or a Hidden Markov model.

44. The apparatus in claim 42 wherein the user model resides on the server and the processor, in response to the stored instructions, provides, through the user model and in response to statistically analyzed server-based log data and the first item or a succession of items, including the first item, downloaded from the server to the client computer, the transition probability for the second item.

45. The apparatus in claim 44 wherein the processor, in response to the stored instructions, determines the transition probability in response to a profile stored on either the client computer or the server.

46. The apparatus in claim 45 wherein the processor, in response to the stored instructions, ascertains the transition probability in response to user activity.

47. The apparatus in claim 42 wherein the processor, in response to the stored instructions, generates, through the user model and in response to user interactivity with the client computer, the transition probability for the second item.

48. The apparatus in claim 42 wherein the interactivity comprises measurements of user scroll, user dwell, or position or user movement of a mouse pointer on the first item as rendered.

49. The apparatus in claim 44 wherein the processor, in response to the stored instructions, generates, through the user model and in response to a pre-defined attribute of the first item, the transition probability for the second item.

50. The apparatus in claim 49 wherein the predefined attribute comprises class, structure or layout of the first page, or content or context of text, graphics or hypertext links on the first item.

51. The apparatus in claim 44 wherein the processor, in response to the stored instructions, generates, through the user model and in response to results returned by a search engine, the transition probability for the second item.

52. The apparatus in claim 51 wherein the results comprise a similarity measure, a keyword in either a returned item from the search engine or a predefined field associated therewith, or content of the returned item.

53. The apparatus in claim 44 wherein the processor, in response to the stored instructions, generates, through the user model and in response to content in the first item or within a predefined field associated with the first item, the transition probability for the second item.

54. The apparatus in claim 53 wherein the predefined field comprises a description, summary or tag field.

55. The apparatus in claim 44 wherein the processor, in response to the stored instructions, generates, through the user model and in response to collaborative filtering of the first item, the transition probability for the second item.

56. The apparatus in claim 44 wherein the processor, in response to the stored instructions, generates, through the user model and in response to characteristics of user eye movement, the transition probability for the second item.

57. The apparatus in claim 56 wherein the user eye movement characteristics comprise real-time measurements of actual eye movement of an individual user or a statistical model of user gaze patterns across a plurality of users.