Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
6085226
Horvitz
July 4, 2000
Title
Method and apparatus for utility-directed prefetching of web pages into local cache using continual computation and user models
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 a probabilistic user model to specify, 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, which promise to provide the largest benefit (expected utility) to the user. Specifically, once a user, at a client computer, enters an address of a desired web page, a set containing web addresses of web pages, that based on the user model are each likely to be accessed next by that user, are determined, with corresponding files therefor prefetched, in order of their expected utility to the user, by the client computer during intervals of low processing activity and low network activity. Expected utility of a page or portion is assessed as a product of rate of refinement in utility of that page or portion to the user multiplied by its transition probability. Once prefetched, these pages or portions are stored in local cache at the client computer for ready access should the user next select any such page or portion.
Inventors:
Horvitz; Eric
(Kirkland,
WA
)
Assignee:
Microsoft Corporation
(Redmond,
CA
)
Appl. No.:
007895
Filed:
January 15, 1998
Current U.S. Class:
709/203
Current International Class:
G06F 17/30 (20060101)
Field of Search:
364/DIG.1,DIG.2 709/200,203,217,223
U.S. Patent Documents
5572643
November 1996
Judson
5727129
March 1998
Barrett et al.
5802292
September 1998
Mogul
5878223
March 1999
Becker et al.
Other References
Cunha et al. "Determing WWW User's Next Access and its Application to Pre-fetching" IEEE, pp. 6-11, Jun. 1997. .
Jiang et al. "Prefetching Links on the WWW" IEEE, pp. 483-489, Aug. 1997. .
Chapter Four "Processes and Threads" of H. Custer, Inside Windows NT (.COPYRGT.1993, Microsoft Press), pp. 83-97. .
G. Cooper, "The Computational Complexity of Bayesian Inference Using Bayesian Belief Networks", Journal of Artificial Intellignece, 42(2):393-405, 1990. .
P. Dagum et al, "Approximating Probalistic Inference in Bayesian Networks is np-hard", Journal of Artificial Intelligence, 60(1):141-153, 1993. .
D. Heckerman et al, "Toward Normative Expert Systems: Part 1 The Pathfinder Project", Methods of Information in Medicine, 31:90-105, 1992. .
M. Henrion et al, "Decision Analysis and Expert Systems", AI Magazine, 12:64-91, Winter 1992. .
E. Horvitz et al, "Flexible Computation for Value of Information in Diagnostic Reasonong", AAA Fall Symposium on Flexible Computation, AAAI, Menlo Park, CA, Nov. 1996. .
E.J. Horvitz, et al, "Decision Theory in Expert Systems and Artificial Intelligence", International Journal of Approximate Reasoning, 2:247-302, 1988. .
E.J. Horvitz, "Reasoning about beliefs and actions under computational resource constraints", Proceedings of Third Workshop on Uncertainty in Artificial Intelligence, pp. 429-444, Seattle, WA, Jul. 1987. .
E.J. Horvitz, "Reasoning Under Varying and Uncertain Resource Constraints", Proceedings AAAI-88 Seventh National Conference on Artificial Intelligence, Minneapolis, MN, pp. 111-116, Morgan Kaufmann, San Mateo, CA, Aug. 1988. .
E.J. Horvitz, "Rational Metareasoning and Compilation for Optimizing Decisions under Bounded Resources", Proceedings of Computational Intelligence 89, Milan, Italy. .
M. Shwe, et al, "Probabalistic Diagnosis Using a Reformulaiton of the Internist-1/QMR Knowledge Base-ii: Evaluation of Diagnostic Performance", Method of Information in Medicine, 30:256-267, 1991..~
Primary Examiner:
Harrell; Robert B.
Attorney, Agent or Firm:
Michaelson & Wallace Michaelson; Peter L.
Claims
I claim:
1. In a client computer system, having a processor and a memory, that, in response to user interaction with the system, requests items of information, as desired by a user, from a server, wherein the client computer or a connection between the client computer exhibits a first period of high utilization followed by a second period of low utilization, a method of obtaining the items of information comprising:
(A) accessing, in response to a request from the user, a first item of information from the server and rendering the first item so accessed to the user; and
(B) while the first item is being so rendered:
(B1) determining, in response to both a predefined aspect of the first item and a predefined user model, a set of items of information which the user is likely to request next from corresponding servers, wherein the determining step comprises:
(B1a) generating a corresponding transition probability estimate for each one of a plurality of items in said set;
(B1b) ascertaining a corresponding flux value, representing a rate of refinement in utility to the user with increased time, for each one of the items in said set; and
(B1c) producing, in response said corresponding probability estimate and said corresponding flux value, a value for a flux-product for said each one of the items in said set so as to form a plurality of flux-product values;
(B2) prefetching ones of the items in said set from the corresponding servers and in descending order of their corresponding flux-product values, wherein the order reflects decreasing expected utility to the user of said ones of the items in the set; and
(B3) storing, in the memory, each of said ones of the items, so prefetched, for subsequent access in the event the user were to request any of said ones of the items.
2. The method in claim 1 further comprising the step of performing, at the onset of the second period, the determining step followed by the prefetching step.
3. The method in claim 2 wherein the first item is a first predetermined quantity of first information, the second item comprises a second predetermined quantity of second information or a pre-defined portion thereof, said first and second informations being different, and the predefined aspect is an address associated with the first quantity of information.
4. The method in claim 3 wherein the server comprises a web server accessible over the connection, wherein the connection comprises either an Internet or an intra-net connection.
5. The method in claim 4 wherein the first and second items are first and second web pages having first and second corresponding addresses, and said predefined aspect is the address of the first web page.
6. The method in claim 5 wherein the user model comprises a model of transition probabilities based on pre-defined data.
7. The method in claim 6 wherein the user model resides on the web server, further comprising the step of providing, through the user model and in response to statistically analyzed server-based log data and the first web page or a succession of web pages, including the first web page, downloaded from the web server to a client computer, a corresponding transition probability for each individual one of the items in the set.
8. The method in claim 7 further comprising the step of generating, through the user model and in response to content in a given item in the set or within a predefined field associated with the given item, a corresponding transition probability for the given item in the set.
9. The method in claim 8 wherein the predefined field comprises a description, summary or tag field.
10. The method in claim 7 further comprising the step of generating, through the user model and in response to collaborative filtering of the first page, a corresponding transition probability for an item in the set.
11. The method in claim 7 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 web server.
12. The method in claim 11 wherein the transition probability determining step of ascertaining the transition probability in response to user activity.
13. The method in claim 7 further comprising the step of generating, through the user model and in response to a pre-defined attribute of the first item, a transition probability for each one of the items in the set.
14. The method in claim 13 wherein the predefined attribute comprises class, structure or layout of the first item, or content or context of text, graphics or hypertext links on the first item.
15. The method in claim 7 further comprising the step of generating, through the user model and in response to results returned by a search engine, a transition probability for each one of the items in the set.
16. The method in claim 15 wherein the results comprise a similarity measure, a keyword in either a returned web page from the search engine or a predefined field associated therewith, or content of the returned web page.
17. The method in claim 7 further comprising the step of generating, through the user model and in response to characteristics of user eye movement, a corresponding transition probability for the given item in the set.
18. The method in claim 17 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.
19. The method in claim 6 wherein the user model, having statistically analyzed log usage data, generates, in response to the predefined aspect of the first item, each of said items, in the set, ordered by likelihood of being accessed next.
20. The method in claim 19 wherein said flux value ascertaining step comprises the step of generating the corresponding flux value for said one item as a predetermined function of a speed at which said one each item is downloaded from the server, a size of said each one item and utility associated with the one item.
21. The method in claim 19 wherein said each one in said set is a web page so as to form a plurality of web pages, and said selecting and prefetching step comprises the step of selecting and prefetching individual ones of the plurality of web pages in descending order of a flux-product associated with each one of said plurality of web pages.
22. The method in claim 19 wherein each one in said set is a screenful of content of an associated web page so as to form a plurality of screenfuls, and said selecting and prefetching step comprises the step of selecting and prefetching individual ones of the plurality of screenfuls in descending order of a flux-product associated with each one of said plurality of screenfuls.
23. The method in claim 19 wherein each one in said set is either a textual or graphical portion of a common web page so as to form respective pluralities of textual and graphical portions of the common web page, and said selecting and prefetching step comprises the steps of:
selecting and prefetching individual ones of a plurality of textual portions in the set and for said common web page in descending order of a flux-product associated with each of said plurality of textual portions; and
selecting and prefetching individual ones of a plurality of graphical portions in the set and for said common web page in descending order of a flux-product associated with each of said plurality of graphical portions.
24. The method in claim 19 wherein each of said individual ones of said items in said set is either a textual or graphical portion of an associated screenful of a web page, said set containing textual and graphical portions for each of a plurality of screenfuls, and said selecting and prefetching step comprises the steps of:
(a) selecting and prefetching individual ones of a plurality of textual portions in the set and for a common one of said screenfuls in descending order of a flux-product associated with each of said plurality of textual portions; and
(b) selecting and prefetching individual ones of a plurality of graphical portions in the set and for said common one screenful in descending order of a flux-product associated with each of said plurality of graphical portions; and
(c) repeating steps (a) and (b) in succession for each remaining individual one of the screenfuls in the set.
25. The method in claim 6 further comprising the step of generating, through the user model and in response to user interactivity with a client computer, a transition probability for each one of the items in the set.
26. The method in claim 25 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.
27. The method in claim 6 wherein the user model further comprises a decision tree derived from a Bayesian network, a Bayesian model or a Hidden Markov model.
28. The method in claim 5 wherein the user model comprises at least one function that provides a transition probability for a hypertext link on the first page in response to user activity, a user profile, structure or content of text or graphics associated with the first web page.
29. The method in claim 28 wherein the user model is further responsive to statistical data obtained on a client computer or the web server.
30. The method in claim 29 wherein the user model further comprises a Bayesian model having a Bayesian network, a Hidden Markov model or a decision tree.
31. The method in claim 5 wherein each individual item in said set is a different web page so as to form a plurality of web pages, and said selecting and prefetching step comprises the step of selecting and prefetching individual ones of the plurality of web pages in descending order of a flux-product associated with each of said plurality of web pages.
32. The method in claim 5 wherein each individual item in said set is a screenful of content of an associated web page so as to form a plurality of screenfuls, and said selecting and prefetching step comprises the step of selecting and prefetching individual ones of the plurality of screenfuls in descending order of a flux-product associated with each of said plurality of screenfuls.
33. The method in claim 5 wherein each individual item in said set is either as textual or graphical portion of a common web page so a to form respective pluralities of textual and graphical portions of the common web page, and said selecting and prefetching step comprises the steps of:
selecting and prefetching individual ones of the plurality of textual portions of said common web page in descending order of a flux-product
associated with each of said plurality of textual portions, and
selecting and prefetching individual ones of the plurality of graphical portions of said common web page in descending order of a flux-product associated with each of said plurality of graphical portions.
34. The method in claim 5 wherein each individual item in said set is either a textual or graphical portion of an associated screenful of a web page, said set containing textual and graphical portions for each of a plurality of screenfuls, and said selecting and prefetching step comprises the steps of:
(a) selecting and prefetching individual ones of a plurality of textual portions in the set and for a common one of said screenfuls in descending order of a flux-product associated with each of said plurality of textual portions;
(b) selecting and prefetching individual ones of a plurality of graphical portions in the set and for said common one screenful in descending order of a flux-product associated with each of said plurality of graphical portions; and
(c) repeating steps (a) and (b) in succession for each remaining individual one of the screenfuls in the set.
35. The method in claim 3 wherein the user model comprises a model of transition probabilities based on pre-defined data.
36. The method in claim 35 further comprising the step of generating, through the user model and in response to a pre-defined attribute of the first item, a transition probability for each one of the items in the set.
37. The method in claim 36 wherein the predefined attribute comprises class, structure or layout of the first item, or content or context of text, graphics or hypertext links on the first item.
38. The method in claim 37 further comprising the step of generating, through the user model and in response to results returned by a search engine, a transition probability for each one of the items in the set.
39. The method in claim 38 wherein the results comprise a similarity measure, a keyword in either a returned web page from the search engine or a predefined field associated therewith, or content of the returned web page.
40. The method in claim 35 further comprising the step of generating, through the user model and in response to user interactivity with the computer system, a transition probability for each one of the items in the set.
41. The method in claim 40 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.
42. The method in claim 35 further comprising the step of generating, through the user model and in response to content in a given item in the set or within a predefined field associated with the given item, a corresponding transition probability for the given item in the set.
43. The method in claim 42 wherein the predefined field comprises a description, summary or tag field.
44. The method in claim 35 further comprising the step of generating, through the user model and in response to characteristics of user eye movement, a corresponding transition probability for the given item in the set.
45. The method in claim 44 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.
46. The method in claim 35 further comprising the step of generating, through the user model and in response to collaborative filtering of the first item, a corresponding transition probability for an item in the set.
47. The method in claim 35 wherein the user model further comprises a decision tree derived from a Bayesian network, a Bayesian model or a Hidden Markov model.
48. The method in claim 35 wherein the user model, having statistically analyzed log usage data, generates, in response to the predefined aspect of the first item, each of said items, in the set, ordered by likelihood of being accessed next.
49. The method in claim 35 wherein said flux value ascertaining step comprises the step of generating the corresponding flux value for said one item as a predetermined function of a speed at which said each one item is downloaded from the server, a size of said each one item and utility associated with the one item.
50. The method in claim 3 wherein the first and second predetermined quantities are separate components of the first and second informations, respectively.
51. A computer readable medium having computer executable instructions stored therein for performing the steps of claim 1.
52. In a computer system, having a processor and a memory, that, in response to user interaction with the system, requests items of information, as desired by a user, from a source accessible by the system, a method, performed by the processor, of obtaining the items of information comprising:
(A) accessing, in response to a request from the user, a first item of information from the source and rendering the first item so accessed to the user; and
(B) while the first item is being so rendered:
(B1) determining, in response to both a predefined aspect of the first item and a predefined user model, a set of items of information which the user is likely to request next from the source, wherein the determining step comprises:
(B1a) generating a corresponding transition probability estimate for each one of a plurality of items in said set;
(B1b) ascertaining a corresponding flux value, representing a rate of refinement in utility to the user with increased time, for each one of the items in said set; and
(B1c) producing, in response said corresponding probability estimate and said corresponding flux value, a value for a flux-product for said each one of the items in said set so as to form a plurality of flux-product values;
(B2) prefetching ones of the items in said set from the source and in descending order of their corresponding flux-product values, wherein the order reflects decreasing expected utility to the user of said ones of the items in the set; and
(B3) storing, in the memory, each of said ones of the items, so prefetched, for subsequent access in the event the user were to request any of said ones of the items.
53. The method in claim 52 wherein the source comprises a remote computer.
54. The method in claim 53 wherein the source comprises a web server accessible over a networked connection, wherein the networked connection comprises either an Internet connection or an intra-net connection.
55. The method in claim 54 wherein the first and second items are first and second web pages having first and second corresponding addresses, and said predefined aspect is the address of the first web page.
56. The method in claim 55 wherein the user model comprises a model of transition probabilities based on pre-defined data.
57. The method in claim 56 wherein the user model resides on the web server, further comprising the step of providing, through the user model and in response to statistically analyzed server-based log data and the first web page or a succession of web pages, including the first web page, downloaded from the web server to a client computer, a corresponding transition probability for each individual one of the items in the set.
58. The method in claim 57 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 web server.
59. The method in claim 58 wherein the transition probability determining step of ascertaining the transition probability in response to user activity.
60. The method in claim 57 further comprising the step of generating, through the user model and in response to a pre-defined attribute of the first item, a transition probability for each one of the items in the set.
61. The method in claim 60 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.
62. The method in claim 57 further comprising the step of generating, through the user model and in response to results returned by a search engine, a transition probability for each one of the items in the set.
63. The method in claim 62 wherein the results comprise a similarity measure, a keyword in either a returned web page from the search engine or a predefined field associated therewith, or content of the returned web page.
64. The method in claim 57 further comprising the step of generating, through the user model and in response to content in a given item in the set or within a predefined field associated with the given item, a corresponding transition probability for the given item in the set.
65. The method in claim 64 wherein the predefined field comprises a description, summary or tag field.
66. The method in claim 57 further comprising the step of generating, through the user model and in response to characteristics of user eye movement, a corresponding transition probability for the given item in the set.
67. The method in claim 66 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.
68. The method in claim 57 further comprising the step of generating, through the user model and in response to collaborative filtering of the first page, a corresponding transition probability for an item in the set.
69. The method in claim 56 further comprising the step of generating, through the user model and in response to user interactivity with a client computer, a transition probability for each one of the items in the set.
70. The method in claim 69 wherein the interactivity comprises measurements of user scroll, user dwell, or position or user movement of a mouse pointer on the first page as rendered.
71. The method in claim 56 wherein the user model, having statistically analyzed log usage data, generates, in response to the predefined aspect of the first item, each of said items, in the set, ordered by likelihood of being accessed next.
72. The method in claim 71 wherein said flux value ascertaining step comprises the step of generating the corresponding flux value for said one item as a predetermined function of a speed at which said each one item is downloaded from the source, a size of said each one item and utility associated with the one item.
73. The method in claim 71 wherein said each one in said set is a web page so as to form a plurality of web pages, and said selecting and prefetching step comprises the step of selecting and prefetching individual ones of the plurality of web pages in descending order of a flux-product associated with each one of said plurality of web pages.
74. The method in claim 71 wherein each one in said set is a screenful of content of an associated web page so as to form a plurality of screenfuls, and said selecting and prefetching step comprises the step of selecting and prefetching individual ones of the plurality of screenfuls in descending order of a flux-product associated with each one of said plurality of screenfuls.
75. The method in claim 71 wherein each one in said set is either a textual or graphical portion of a common web page so as to form respective pluralities of textual and graphical portions of the common web page, and said selecting and prefetching step comprises the steps of:
selecting and prefetching individual ones of a plurality of textual portions in the set and for said common web page in descending order of a flux-product associated with each of said plurality of textual portions; and
selecting and prefetching individual ones of a plurality of graphical portions in the set and for said common web page in descending order of a flux-product associated with each of said plurality of graphical portions.
76. The method in claim 71 wherein each of said individual ones of said items in said set is either a textual or graphical portion of an associated screenful of a web page, said set containing textual and graphical portions for each of a plurality of screenfuls, and said selecting and prefetching step comprises the steps of:
(a) selecting and prefetching individual ones of a plurality of textual portions in the set and for a common one of said screenfuls in descending order of a flux-product associated with each of said plurality of textual portions; and
(b) selecting and prefetching individual ones of a plurality of graphical portions in the set and for said common one screenful in descending order of a flux-product associated with each of said plurality of graphical portions; and
(c) repeating steps (a) and (b) in succession for each remaining individual one of the screenfuls in the set.
77. The method in claim 56 wherein the user model further comprises a decision tree derived from a Bayesian network, a Bayesian model or a Hidden Markov model.
78. The method in claim 55 wherein the user model comprises at least one function that provides a transition probability for a hypertext link on the first page in response to user activity, a user profile, structure or content of text or graphics associated with the first web page.
79. The method in claim 78 wherein the user model is further responsive to statistical data obtained on a client computer or the web server.
80. The method in claim 79 wherein the user model further comprises a Bayesian model having a Bayesian network, a Hidden Markov model or a decision tree.
81. The method in claim 55 wherein each individual item in said set is a different web page so as to form a plurality of web pages, and said selecting and prefetching step comprises the step of selecting and prefetching individual ones of the plurality of web pages in descending order of a flux-product associated with each of said plurality of web pages.
82. The method in claim 55 wherein each individual item in said set is a screenful of content of an associated web page so as to form a plurality of screenfuls, and said selecting and prefetching step comprises the step of selecting and prefetching individual ones of the plurality of screenfuls in descending order of a flux-product associated with each of said plurality of screenfuls.
83. The method in claim 55 wherein each individual item in said set is either a textual or graphical portion of a common web page so as to form respective pluralities of textual and graphical portions of the common web page, and said selecting and prefetching step comprises the steps of:
selecting and prefetching individual ones of the plurality of textual portions of said common web page in descending order of a flux-product associated with each of said plurality of textual portions, and
selecting and prefetching individual ones of the plurality of graphical portions of said common web page in descending order of a flux-product associated with each of said plurality of graphical portions.
84. The method in claim 55 wherein each individual item in said set is either a textual or graphical portion of an associated screenful of a web page, said set containing textual and graphical portions for each of a plurality of screenfuls, and said selecting and prefetching step comprises the steps of:
(a) selecting and prefetching individual ones of a plurality of textual portions in the set and for a common one of said screenfuls in descending order of a flux-product associated with each of said plurality of textual portions;
(b) selecting and prefetching individual ones of a plurality of graphical portions in the set and for said common one screenful in descending order of a flux-product associated with each of said plurality of graphical portions; and
(c) repeating steps (a) and (b) in succession for each remaining individual one of the screenfuls in the set.
85. The method in claim 52 wherein the first item is a first predetermined quantity of first information, the second item comprises a second predetermined quantity of second information or a pre-defined portion thereof, said first and second informations being different, and the predefined aspect is an address associated with the first quantity of information.
86. The method in claim 85 wherein the user model comprises a model of transition probabilities based on pre-defined data.
87. The method in claim 86 further comprising the step of generating, through the user model and in response to user interactivity with the computer system, a transition probability for each one of the items in the set.
88. The method in claim 87 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.
89. The method in claim 86 further comprising the step of generating, through the user model and in response to a pre-defined attribute of the first item, a transition probability for each one of the items in the set.
90. The method in claim 89 wherein the predefined attribute comprises class, structure or layout of the first item, or content or context of text, graphics or hypertext links on the first item.
91. The method in claim 86 further comprising the step of generating, through the user model and in response to results returned by a search engine, a transition probability for each one of the items in the set.
92. The method in claim 91 wherein the results comprise a similarity measure, a keyword in either a returned web page from the search engine or a predefined field associated therewith, or content of the returned web page.
93. The method in claim 86 further comprising the step of generating, through the user model and in response to content in a given item in the set or within a predefined field associated with the given item, a corresponding transition probability for the given item in the set.
94. The method in claim 93 wherein the predefined field comprises a description, summary or tag field.
95. The method in claim 86 further comprising the step of generating, through the user model and in response to characteristics of user eye movement, a corresponding transition probability for the given item in the set.
96. The method in claim 95 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.
97. The method in claim 86 further comprising the step of generating, through the user model and in response to collaborative filtering of the first item, a corresponding transition probability for an item in the set.
98. The method in claim 86 wherein the user model further comprises a decision tree derived from a Bayesian network, a Bayesian model or a Hidden Markov model.
99. The method in claim 86 wherein the user model, having statistically analyzed log usage data, generates, in response to the predefined aspect of the first item, each of said items, in the set, ordered by likelihood of being accessed next.
100. The method in claim 86 wherein said flux value ascertaining step comprises the step of generating the corresponding flux value for said one item as a predetermined function of a speed at which said each one item is downloaded from the source, a size of said each one item and utility associated with the one item.
101. The method in claim 85 wherein the first and second predetermined quantities are separate components of the first and second informations, respectively.
102. A computer readable medium having computer executable instructions stored therein for performing the steps of claim 52.
103. Apparatus for that, in response to user interaction with the system, requests items of information, as desired by a user, from a source accessible by the system, the apparatus comprising:
(A) a processor; and
(B) a memory, connected to the processor, having a computer executable program stored therein;
(C) wherein, in response to the stored instructions, the processor:
(C1) accesses, in response to a request from the user, a first item of information from the source and rendering the first item so accessed to the user; and
(C2) while the first item is being so rendered:
(C2a) determines, in response to both a predefined aspect of the first item and a predefined user model, a set of items of information which the user is likely to request next from the source, wherein the processor:
(C2a1) generates a corresponding transition probability estimate for each one of a plurality of items in said set;
(C2a2) ascertains a corresponding flux value, representing a rate of refinement in utility to the user with increased time, for each one of the items in said set; and
(C2a3) produces, in response said corresponding probability estimate and said corresponding flux value, a value for a flux-product for said each one of the items in said set so as to form a plurality of flux-product values;
(C2b) prefetches ones of the items in said set from the source and in descending order of their corresponding flux-product values, wherein the order reflects decreasing expected utility to the user of said ones of the items in the set; and
(C2c) stores, in the memory, each of said ones of the items, so prefetched, for subsequent access in the event the user were to request any of said ones of the items.
104. The apparatus in claim 103 wherein the source is a remote computer.
105. The apparatus in claim 104 wherein the source is a web server accessible over a networked connection, wherein the networked connection comprises either an Internet connection or an intra-net connection.
106. The apparatus in claim 105 wherein the first and second items are first and second web pages having first and second corresponding addresses, and said predefined aspect is the address of the first web page.
107. The apparatus in claim 106 wherein the user model comprises a model of transition probabilities based on pre-defined data.
108. The apparatus in claim 107 wherein the user model resides on the web 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 web page or a succession of web pages, including the first web page, downloaded from the web server to a client computer, a corresponding transition probability for each individual one of the items in the set.
109. The apparatus in claim 108 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 web server.
110. The apparatus in claim 109 wherein the processor, in response to the stored instructions, ascertains the transition probability in response to user activity.
111. The apparatus in claim 108 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, a transition probability for each one of the items in the set.
112. The apparatus in claim 111 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.
113. The apparatus in claim 108 wherein the processor, in response to the stored instructions, generates, through the user model and in response to results returned by a search engine, a transition probability for each one of the items in the set.
114. The apparatus in claim 113 wherein the results comprise a similarity measure, a keyword in either a returned web page from the search engine or a predefined field associated therewith, or content of the returned web page.
115. The apparatus in claim 108 wherein the processor, in response to the stored instructions, generates, through the user model and in response to content in a given item in the set or within a predefined field associated with the given item, a corresponding transition probability for the given item in the set.
116. The apparatus in claim 115 wherein the predefined field comprises a description, summary or tag field.
117. The apparatus in claim 108 wherein the processor, in response to the stored instructions, generates, through the user model and in response to characteristics of user eye movement, a corresponding transition probability for the given item in the set.
118. The apparatus in claim 117 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.
119. The apparatus in claim 108 wherein the processor, in response to the stored instructions, generates, through the user model and in response to collaborative filtering of the first page, a corresponding transition probability for an item in the set.
120. The apparatus in claim 107 wherein the user model, having statistically analyzed log usage data, generates, in response to the predefined aspect of the first item, each of said items, in the set, ordered by likelihood of being accessed next.
121. The apparatus in claim 120 wherein the processor, in response to the stored instructions, generates the corresponding flux value for said one item as a predetermined function of a speed at which said each one item is downloaded from the source, a size of said each one item and utility associated with the one item.
122. The apparatus in claim 120 wherein said each one in said set is a web page so as to form a plurality of web pages, and wherein the processor, in response to the stored instructions, selects and prefetches individual ones of the plurality of web pages in descending order of a flux-product associated with each one of said plurality of web pages.
123. The apparatus in claim 120 wherein each one in said set is a screenful of content of an associated web page so as to form a plurality of screenfuls, and wherein the processor, in response to the stored instructions, selects and prefetches individual ones of the plurality of screenfuls in descending order of a flux-product associated with each one of said plurality of screenfuls.
124. The apparatus in claim 120 wherein each one in said set is either a textual or graphical portion of a common web page so as to form respective pluralities of textual and graphical portions of the common web page, and wherein the processor, in response to the stored instructions:
selects and prefetches individual ones of a plurality of textual portions in the set and for said common web page in descending order of a flux-product associated with each of said plurality of textual portions; and
selects and prefetches individual ones of a plurality of graphical portions in the set and for said common web page in descending order of a flux-product associated with each of said plurality of graphical portions.
125. The apparatus in claim 120 wherein each of said individual ones of said items in said set is either a textual or graphical portion of an associated screenful of a web page, said set containing textual and graphical portions for each of a plurality of screenfuls, and wherein the processor, in response to the stored instructions:
(a) selects and prefetches individual ones of a plurality of textual portions in the set and for a common one of said screenfuls in descending order of a flux-product associated with each of said plurality of textual portions; and
(b) selects and prefetches individual ones of a plurality of graphical portions in the set and for said common one screenful in descending order of a flux-product associated with each of the said plurality of graphical portions; and
(c) repeats operations (a) and (b) in succession for each remaining individual one of the screenfuls in the set.
126. The apparatus in claim 107 wherein the processor, in response to the stored instructions, generates, through the user model and in response to user interactivity with a client computer, a transition probability for each one of the items in the set.
127. The apparatus in claim 126 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.
128. The apparatus in claim 107 wherein the user model further comprises a decision tree derived from a Bayesian network, a Bayesian model or a Hidden Markov model.
129. The apparatus in claim 106 wherein the user model comprises at least one function that provides a transition probability for a hypertext link on the first page in response to user activity, a user profile, structure or content of text or graphics associated with the first web page.
130. The apparatus in claim 129 wherein the user model is further responsive to statistical data obtained on a client computer or the web server.
131. The apparatus in claim 130 wherein the user model further comprises a Bayesian model having a Bayesian network, a Hidden Markov model or a decision tree.
132. The apparatus in claim 106 wherein each individual item in said set is a different web page so as to form a plurality of web pages, and wherein the processor, in response to the stored instructions, selects and prefetches individual ones of the plurality of web pages in descending order of a flux-product associated with each of said plurality of web pages.
133. The apparatus in claim 132 wherein each individual item in said set is either a textual or graphical portion of a common web page so as to form respective pluralities of textual and graphical portions of the common web page, and wherein the processor, in response to the stored instructions:
selects and prefetches individual ones of the plurality of textual portions of said common web page in descending order of a flux-product associated with each of said plurality of textual portions, and
selects and prefetches individual ones of the plurality of graphical portions of said common web page in descending order of a flux-product associated with each of said plurality of graphical portions.
134. The apparatus in claim 132 wherein each individual item in said set is a screenful of content of an associated web page so as to form a plurality of screenfuls, and wherein the processor, in response to the stored instructions, selects and prefetches individual ones of the plurality of screenfuls in descending order of a flux-product associated with each of said plurality of screenfuls.
135. The apparatus in claim 132 wherein each individual item in said set is either a textual or graphical portion of an associated screenful of a web page, said set containing textual and graphical portions for each of a plurality of screenfuls, and wherein the processor, in response to the stored instructions:
(a) selects and prefetches individual ones of a plurality of textual portions in the set and for a common one of said screenfuls in descending order of a flux-product associated with each of said plurality of textual portions;
(b) selects and prefetches individual ones of a plurality of graphical portions in the set and for said common one screenful in descending order of a flux-product associated with each of said plurality of graphical portions; and
(c) repeats operations (a) and (b) in succession for each remaining individual one of the screenfuls in the set.
136. The apparatus in claim 103 wherein the first item is a first predetermined quantity of first information, the second item comprises a second predetermined quantity of second information or a pre-defined portion thereof, said first and second informations being different, and the predefined aspect is an address associated with the first quantity of information.
137. The apparatus in claim 136 wherein the user model comprises a model of transition probabilities based on pre-defined data.
138. The apparatus in claim 137 wherein the processor, in response to the stored instructions, generates, through the user model and in response to user interactivity with the computer system, a transition probability for each one of the items in the set.
139. The apparatus in claim 138 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.
140. The apparatus in claim 137 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, a transition probability for each one of the items in the set.
141. The apparatus in claim 140 wherein the predefined attribute comprises class, structure or layout of the first item, or content or context of text, graphics or hypertext links on the first item.
142. The apparatus in claim 137 wherein the processor, in response to the stored instructions, generates, through the user model and in response to results returned by a search engine, a transition probability for each one of the items in the set.
143. The apparatus in claim 142 wherein the results comprise a similarity measure, a keyword in either a returned web page from the search engine or a predefined field associated therewith, or content of the returned web page.
144. The apparatus in claim 137 wherein the processor, in response to the stored instructions, generates, through the user model and in response to content in a given item in the set or within a predefined field associated with the given item, a corresponding transition probability for the given item in the set.
145. The apparatus in claim 144 wherein the predefined field comprises a description, summary or tag field.
146. The apparatus in claim 137 wherein the processor, in response to the stored instructions, generates, through the user model and in response to characteristics of user eye movement, a corresponding transition probability for the given item in the set.
147. The apparatus in claim 146 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.
148. The apparatus in claim 137 wherein the processor, in response to the stored instructions, generates, through the user model and in response to collaborative filtering of the first item, a corresponding transition probability for an item in the set.
149. The apparatus in claim 137 wherein the user model further comprises a decision tree derived from a Bayesian network, a Bayesian model or a Hidden Markov model.
150. The apparatus in claim 137 wherein the user model, having statistically analyzed log usage data, generates, in response to the predefined aspect of the first item, each of said items, in the set, ordered by likelihood of being accessed next.
151. The apparatus in claim 137 wherein the processor, in response to the stored instructions, generates the corresponding flux value for said one item as a predetermined function of a speed at which said each one item is downloaded from the source, a size of said each one item and utility associated with the one item.
152. The apparatus in claim 136 wherein the first and second predetermined quantities are separate components of the first and second informations, respectively.
153. Apparatus for a client computer system, having a processor and a memory, that, in response to user interaction with the system, requests items of information, as desired by a user, from a server, wherein the client computer or a connection between the client computer exhibits a first period of high utilization followed by a second period of low utilization, the client computer comprising:
(A) a processor; and
(B) a memory, connected to the processor, having a computer executable program stored therein;
(C) wherein, in response to the stored instructions, the processor:
(C1) accesses, in response to a request from the user, a first item of information from the server and rendering the first item so accessed to the user; and
(C2) while the first item is being so rendered:
(c2a) determines, in response to both a predefined aspect of the first item and a predefined user model, a set of items of information which the user is likely to request next from corresponding servers, wherein the processor:
(C2a1) generates a corresponding transition probability estimate for each one of a plurality of items in said set;
(C2a2) ascertains a corresponding flux value, representing a rate of refinement in utility to the user with increased time, for each one of the items in said set; and
(C2a3) produces, in response said corresponding probability estimate and said corresponding flux value, a value for a flux-product for said each one of the items in said set so as to form a plurality of flux-product values;
(C2b) prefetches ones of the items in said set from the corresponding servers and in descending order of their corresponding flux-product values, wherein the order reflects decreasing expected utility to the user of said ones of the items in the set; and
(C2c) stores, in the memory, each of said ones of the items, so prefetched, for subsequent access in the event the user were to request any of said ones of the items.
154. The apparatus in claim 153 wherein the processor, in response to the stored instructions, performs, at the onset of the second period, the determining operation followed by the prefetching operation.
155. The apparatus in claim 154 wherein the server comprises a web server accessible over the connection, wherein the connection comprises either an Internet or an intra-net connection.
156. The apparatus in claim 155 wherein the first and second items are first and second web pages having first and second corresponding addresses, and said predefined aspect is the address of the first web page.
157. The apparatus in claim 156 wherein the user model comprises a model of transition probabilities based on pre-defined data.
158. The apparatus in claim 157 wherein the user model resides on the web 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 web page or a succession of web pages, including the first web page, downloaded from the web server to a client computer, a corresponding transition probability for each individual one of the items in the set.
159. The apparatus in claim 158 wherein the processor, in response to the stored instructions, generates, through the user model and in response to
collaborative filtering of the first page, a corresponding transition probability for an item in the set.
160. The apparatus in claim 158 wherein the processor, in response to the stored instructions, generates, through the user model and in response to characteristics of user eye movement, a corresponding transition probability for the given item in the set.
161. The apparatus in claim 158 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, a transition probability for each one of the items in the set.
162. The apparatus in claim 161 wherein the predefined attribute comprises class, structure or layout of the first item, or content or context of text, graphics or hypertext links on the first item.
163. The apparatus in claim 158 wherein the processor, in response to the stored instructions, generates, through the user model and in response to results returned by a search engine, a transition probability for each one of the items in the set.
164. The apparatus in claim 163 wherein the results comprise a similarity measure, a keyword in either a returned web page from the search engine or a predefined field associated therewith, or content of the returned web page.
165. The apparatus in claim 158 wherein the processor, in response to the stored instructions, generates, through the user model and in response to content in a given item in the set or within a predefined field associated with the given item, a corresponding transition probability for the given item in the set.
166. The apparatus in claim 165 wherein the predefined field comprises a description, summary or tag field.
167. The apparatus in claim 160 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.
168. The apparatus in claim 158 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 web server.
169. The apparatus in claim 168 wherein the processor, in response to the stored instructions, ascertains the transition probability in response to user activity.
170. The apparatus in claim 157 wherein the user model, having statistically analyzed log usage data, generates, in response to the predefined aspect of the first item, each of said items, in the set, ordered by likelihood of being accessed next.
171. The apparatus in claim 170 wherein the processor, in response to the stored instructions, generates the corresponding flux value for said one item as a predetermined function of a speed at which said each one item is downloaded from the server, a size of said each one item and utility associated with the one item.
172. The apparatus in claim 170 wherein said each one in said set is a web page so as to form a plurality of web pages, and wherein the processor, in response to the stored instructions, selects and prefetches individual ones of the plurality of web pages in descending order of a flux-product associated with each one of said plurality of web pages.
173. The apparatus in claim 170 wherein each one in said set is a screenful of content of an associated web page so as to form a plurality of screenfuls, and wherein the processor, in response to the stored instructions, selects and prefetches individual ones of the plurality of screenfuls in descending order of a flux-product associated with each one of said plurality of screenfuls.
174. The apparatus in claim 170 wherein each one in said set is either a textual or graphical portion of a common web page so as to form respective pluralities of textual and graphical portions of the common web page, and wherein the processor, in response to the stored instructions:
selects and prefetches individual ones of a plurality of textual portions in the set and for said common web page in descending order of a flux-product associated with each of said plurality of textual portions; and
selects and prefetches individual ones of a plurality of graphical portions in the set and for said common web page in descending order of a flux-product associated with each of said plurality of graphical portions.
175. The apparatus in claim 170 wherein each of said individual ones of said items in said set is either a textual or graphical portion of an associated screenful of a web page, said set containing textual and graphical portions for each of a plurality of screenfuls, and wherein the processor, in response to the stored instructions:
(a) selects and prefetches individual ones of a plurality of textual portions in the set and for a common one of said screenfuls in descending order of a flux-product associated with each of said plurality of textual portions; and
(b) selects and prefetches individual ones of a plurality of graphical portions in the set and for said common one screenful in descending order of a flux-product associated with each of said plurality of graphical portions; and
(c) repeats operations (a) and (b) in succession for each remaining individual one of the screenfuls in the set.
176. The apparatus in claim 157 wherein the processor, in response to the stored instructions, generates, through the user model and in response to user interactivity with a client computer, a transition probability for each one of the items in the set.
177. The apparatus in claim 176 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.
178. The apparatus in claim 157 wherein the user model further comprises a decision tree derived from a Bayesian network, a Bayesian model or a Hidden Markov model.
179. The apparatus in claim 156 wherein the user model comprises at least one function that provides a transition probability for a hypertext link on the first page in response to user activity, a user profile, structure or content of text or graphics associated with the first web page.
180. The apparatus in claim 179 wherein the user model is further responsive to statistical data obtained on a client computer or the web server.
181. The apparatus in claim 180 wherein the user model further comprises a Bayesian model having a Bayesian network, a Hidden Markov model or a decision tree.
182. The apparatus in claim 156 wherein each individual item in said set is a different web page so as to form a plurality of web pages, and wherein the processor, in response to the stored instructions, selects and prefetches individual ones of the plurality of web pages in descending order of a flux-product associated with each of said plurality of web pages.
183. The apparatus in claim 182 wherein each individual item in said set is a screenful of content of an associated web page so as to form a plurality of screenfuls, and wherein the processor, in response to the stored instructions, selects and prefetches individual ones of the plurality of screenfuls in descending order of a flux-product associated with each of said plurality of screenfuls.
184. The apparatus in claim 182 wherein each individual item in said set is either a textual or graphical portion of a common web page so as to form respective pluralities of textual and graphical portions of the common web page, and wherein the processor, in response to the stored instructions:
selects and prefetches individual ones of the plurality of textual portions of said common web page in descending order of a flux-product associated with each of said plurality of textual portions, and
selects and prefetches individual ones of the plurality of graphical portions of said common web page in descending order of a flux-product associated with each of said plurality of graphical portions.
185. The apparatus in claim 182 wherein each individual item in said set is either a textual or graphical portion of an associated screenful of a web page, said set containing textual and graphical portions for each of a plurality of screenfuls, and wherein the processor, in response to the stored instructions:
(a) selects and prefetches individual ones of a plurality of textual portions in the set and for a common one of said screenfuls in descending order of a flux-product associated with each of said plurality of textual portions;
(b) selects and prefetches individual ones of a plurality of graphical portions in the set and for said common one screenful in descending order of a flux-product associated with each of said plurality of graphical portions; and
(c) repeats operations (a) and (b) in succession for each remaining individual one of the screenfuls in the set.
186. The apparatus in claim 154 wherein the first item is a first predetermined quantity of first information, the second item comprises a second predetermined quantity of second information or a pre-defined portion thereof, said first and second informations being different, and the predefined aspect is an address associated with the first quantity of information.
187. The apparatus in claim 186 wherein the user model comprises a model of transition probabilities based on pre-defined data.
188. The apparatus in claim 187 wherein the processor, in response to the stored instructions, generates, through the user model and in response to user interactivity with the computer system, a transition probability for each one of the items in the set.
189. The apparatus in claim 188 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.
190. The apparatus in claim 187 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, a transition probability for each one of the items in the set.
191. The apparatus in claim 190 wherein the predefined attribute comprises class, structure or layout of the first item, or content or context of text, graphics or hypertext links on the first item.
192. The apparatus in claim 187 wherein the processor, in response to the stored instructions, generates, through the user model and in response to results returned by a search engine, a transition probability for each one of the items in the set.
193. The apparatus in claim 192 wherein the results comprise a similarity measure, a keyword in either a returned web page from the search engine or a predefined field associated therewith, or content of the returned web page.
194. The apparatus in claim 187 wherein the processor, in response to the stored instructions, generates, through the user model and in response to content in a given item in the set or within a predefined field associated with the given item, a corresponding transition probability for the given item in the set.
195. The apparatus in claim 194 wherein the predefined field comprises a description, summary or tag field.
196. The apparatus in claim 187 wherein the processor, in response to the stored instructions, generates, through the user model and in response to characteristics of user eye movement, a corresponding transition probability for the given item in the set.
197. The apparatus in claim 196 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.
198. The apparatus in claim 187 wherein the user model, having statistically analyzed log usage data, generates, in response to the predefined aspect of the first item, each of said items, in the set, ordered by likelihood of being accessed next.
199. The apparatus in claim 198 wherein the processor, in response to the stored instructions, generates the corresponding flux value for said one item as a predetermined function of a speed at which said each one item is downloaded from the server, a size of said each one item and utility associated with the one item.
200. The apparatus in claim 187 wherein the processor, in response to the stored instructions, generates, through the user model and in response to collaborative filtering of the first item, a corresponding transition probability for an item in the set.
201. The apparatus in claim 187 wherein the user model further comprises a decision tree derived from a Bayesian network, a Bayesian model or a Hidden Markov model.
202. The apparatus in claim 186 wherein the first and second predetermined quantities are separate components of the first and second informations, respectively.
Description
NOTICE OF COPYRIGHTED MATERIAL IN THE DISCLOSURE
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE DISCLOSURE
1. Field of the Invention
The invention relates to a technique, specifically apparatus and accompanying methods for use therein, that optimally, through continual computation, uses available computer resources including but not limited to periods of low processing and low network activity, such as idle time, for prefetching web pages, or pre-selected portions thereof, into local cache of a client computer. This technique, particularly though not exclusively suited for use in a web browser, utilizes, e.g., a probabilistic or statistical user model to specify, at any one time, those pages that are to be prefetched given information including, e.g., a web page currently being rendered to a user, content and structure of that particular web page, a history of web pages visited by the user, user background, and user actions. In addition, advantageously, this technique prematurely terminates a current information download for the user in favor of prefetching a web page of future interest to that user whenever the latter page exhibits greater incremental utility to the user than does continuing the current download.
2. Description of the Prior Art
Currently, Internet usage, and particularly that of the World Wide Web (henceforth referred to as simply the "web"), is growing explosively, particularly as the number of web sites and users that have access to the Internet continues to rapidly expand.
In essence, after establishing a suitable network connection the Internet, a user can easily employ a graphical web browser, such as the Internet Explorer ("IE") browser presently available from Microsoft Corporation of Redmond, Wash., to connect to a web site by simply supplying an address (known as a URL or uniform resource locator). The URL identifies both the location of the site and a page of information at that site. Each web site stores at least one, and often times substantially more pages all arranged in a pre-defined hierarchy. Pages, in this context, refer to content accessed via a URL, including, e.g., text, graphics, and other information. Once a user supplies a URL, the browser sends an appropriate command to the site storing that page to access and download that page; the site then sends a file containing information for that page. As the file is received by the browser, the browser assembles and displays the page on a monitor for the client computer. Once the content associated with the page is fully or sufficiently rendered, the user can then point his(her) mouse to a suitable hypertext link, button or other suitable user input field (whichever here implements a "hot-link") displayed on that page and then, through, e.g., a mouse "click", effectively download and display another desired page in succession until the user has finished his(her) visit to that site. A hot-link specifies an address of an associated page, regardless of the web site at which that page is situated. Consequently, by simply and successively pointing and "clicking" his(her) mouse at an appropriate hot-link for each one of a number of desired web pages, the user can readily retrieve each desired page in succession from its corresponding web site and effortlessly jump from site to site, regardless of where those sites are physically located.
While a considerable amount of information can be downloaded from a web site for display by a browser, in practice, various factors exist which retard the speed at which the content from a page or from successive pages can be displayed on a client computer--often to the frustration of a user situated there.
One such factor lies with the nature of traditional personal computing itself. Specifically, personal computing applications, such as web browsers, word processors and spreadsheets, heavily rely on continual interactivity between the user and the computer. Inasmuch as a human being provides information, i.e. an entry, into a personal computer at a substantially slower rate than a rate at which the computer is able to accept and process the entry, computing activity in a personal computer is typically characterized by bursts of user input associated with relatively high processing or network activity, during which a user entry is being actively processed or information is being communicated, interspersed with intervals, usually considerably much longer, of relatively low activity during which the computer waits for another user entry. Oftentimes, during the latter intervals, relatively low priority tasks, such as background or overhead processing of one form or another, execute or, if no such tasks then exist, the computer simply resides in an idle state pending receipt of a user entry. Hence, some degree of available processing or networking capacity may either exist and not be used by virtue of the computer or network simply idling, or be allocated to relatively unimportant (i.e. low priority) tasks that could readily be deferred so as to allocate computational effort to potential future tasks. In the case of executing a web browser, the amount of time a personal computer and network spends in processing and communicating a user request, such as entry of a URL and fetch and display of content from a web page associated therewith, may be shorter than an interval of time during which a user both examines content or a portion of the content from that page, once displayed, without providing any entry (i.e. "dwells" on the page) and then fully completes or selects a next entry, e.g. by clicking on a next successive hypertext link or button.
Moreover, a conventional web browser and a user collectively and principally operate on a time-staggered basis with no overlap, i.e. they operate serially. Operating in this manner, while procedurally rather simple, is rather inefficient and wasteful of processing time. Essentially, while the computer and the browser operate in a high activity state to process user input and, by doing so, fetch a page from a web site and then display that page, the user simply waits until the browser finishes assembling that page on the monitor or attempts to browse portions of a page that have been transmitted and rendered while a download continues. Page assembly completes either when the page is fully assembled and rendered, or when the user prematurely terminates further page assembly by suitably issuing a termination signal to the browser such as a "Stop" or "Back" command. In many situations, a user is only interested in reviewing a portion of total content associated with a URL, often being most interested in representative or overview material which is typically transmitted initially. Commonly, where a user searches for information that may reside on one or several URLs, among scores of potentially valuable pages, the user only spends time reviewing a small portion of content from a URL to decide whether the content associated with that URL is relevant. While the user dwells on content that has
already been completely downloaded and displayed, and pending completion of any user input, e.g. while a mouse is being manipulated or data entered through a keyboard, the computer and browser are both operating in a low activity state (the former idling or executing low priority tasks, the latter idling) pending a signal from the user, typically a mouse click, that (s)he has completed entry of that input and requests that the input be suitably processed. In cases where all of the content associated with a URL is not yet downloaded, networking resources may be wasted retrieving additional components of a page that will not provide great value to the user. Thus, processing time may be wasted by the computer and browser in either simply waiting for successive user input once a current page has been assembled and rendered, or by using computer, network, and server resources to continue to retrieve additional information associated with a URL that may be of little or no value to the user.
Hence, in a personal computer environment, one might think that if a personal computer, and specifically a web browser executing there, could utilize available processing capacity that would otherwise be wasted (either by virtue of idling or being allocated to low priority tasks) to process future page requests in some fashion, the throughput of displayed pages could advantageously increase to the benefit of the user. However, the art appears to be devoid of any teachings that dictate just how this could be accomplished.
Therefore, a need exists in the art for a technique, specifically apparatus and accompanying methods, for use with a personal computer, and particularly a web browser executing there, that can process page requests using processing and networking capacity, available during intervals of relatively low activity, such as, e.g. idle CPU or network capacity, that would otherwise be wasted, or for allocating varying amounts of networking resources away from downloading and display of components of a requested URL and in favor of downloading content associated with potential future URL requests. Advantageously, use of such a technique is likely to significantly increase the rate at which pages are typically displayed to a user, thus reducing user frustration and increasing user satisfaction.
SUMMARY OF THE INVENTION
My inventive technique satisfies this need for prefetching and caching web pages (or, generally speaking, information), as determined by a user model, that may be selected in the future by the user or that contain content that may be of interest to the user based upon current and/or, e.g., prior interaction of the user with, e.g., his(her) client computer.
Broadly speaking and in accordance with my invention, a client computer prefetches such web pages of interest (of other information) for subsequent access, potentially while a current web page is being rendered for, e.g., for user review, on a local display.
Advantageously, my inventive technique uses available resources that would otherwise be available during periods of low activity, i.e. during intervals of what otherwise would be periods of low (e.g. idle) processing time (e.g. during which a web page is being displayed) and/or low (e.g. idle) network activity to select, prefetch and cache appropriate pages or selected portions of those pages. Alternatively, such current resources that would be otherwise be applied to continuing to download additional portions associated with a currently selected page can be allocated instead to the task of prefetching and caching pages that may be selected in the future.
Furthermore and in accordance with the broad teachings of my invention, the particular pages or portions of pages (or, generally speaking, items of information or predefined portions of those pages) that are pre-fetched (referred to as "future" pages) are those which would then provide the highest benefit (expected utility) to a user. These potential future pages are determined by forecasting the behavior of the user under uncertainty with user models, that employ rules, functions, data analysis, or combinations thereof to provide estimates of probabilities (likelihood) that the user will access, in the future, each of those particular pages for viewing, e.g., transition to that page from a current page, or transition to that page later, i.e. in a current session or within a given time horizon of that session. The user models can rely on, e.g., a function(s) of current page structure and content, recent sequences of pages downloaded to the user, descriptions of long-term or short-term interests of the user, user background, the behavior of the user in interacting with the computer or previously downloaded content, and one or more usage statistics available from a server or from the user's computer.
Specifically, once a user, at a client computer, enters an address (e.g. a URL) of a desired web page, a set containing web addresses of pages, that based on the user model are each likely to be accessed next, in the same session, or within a given time horizon thereof by that user, are determined, with corresponding files for those pages prefetched by the client computer during intervals of low processing activity and/or low network activity, or when an incremental rate of change in utility, of continuing current activity is determined to be lower than an expected value of the utility of fetching potential future content. Once prefetched, the file for each page is stored in local cache at the client computer for ready access should the user next select that particular page. As successive web pages are selected by the user and displayed, the immediately prior set of files for prefetched pages can be over-written by files for a current set of prefetched pages. To further improve performance, the files for those web pages that are common to both sets, once prefetched and stored for the prior set, need not be prefetched again as part of the current set. For a given user, the user model can be, e.g., a simple rank ordering of URLs based on log data of page transitions across all individuals who visit a given web site containing those pages or a Bayesian model of the preferences of that user encoded in terms of, e.g., numeric conditional probabilities, of selecting, e.g., given a displayed page, other pages. This model can reside in a web server, a client or across both.
Apart from choosing different web page components, e.g., textual or graphics or individual screenfuls of a common page, to prefetch, on a fundamental level, my present invention also encompasses the concept of prematurely terminating a current information download, in favor of prefetching a web page that will be accessed in the future, such as during the current session or within a given time horizon, where the expected refinement in the rate of change in utility (incremental utility) to the user in prefetching the future page is greater than the incremental utility associated with continuing the current information download. Proceeding in this fashion advantageously permits a browser to terminate an information download which provides diminishing utility to a user in favor of then fetching or prefetching a different page of greater interest.
In accordance with these inventive teachings, a browser, through use of, e.g., a probabilistic user model, can compare rate of refinement in utility provided by a current information download, i.e. a web page currently being fetched, and compare that rate against a discounted flux-product associated with a web page to which the user is likely to transition in the future (i.e. a "future" web page). Whenever the discounted flux-product of the latter page exceeds the rate of refinement with time then being provided by continuing to download the former page, computational or networking resources are deallocated from the current information download and allocated (applied) to prefetching and storing the future web page. Consequently, downloading of the current information download former is prematurely terminated or slowed (retarded) in favor of then prefetching the future web page. Generally speaking, any current computational task, not just fetching and rendering of web pages, which can be interrupted and for which a rate of refinement in value with time can be ascertained can be prematurely terminated or slowed in accordance with my inventive teachings in favor of prefetching a future web page that, for the user, then exhibits a greater discounted flux-product than does the rate of refinement in value with time of the current task.
As a feature, my invention can take account of increased information content and importance to a user of separate portions of a common web page, or of different portions of differing pages. In particular, and for a common page, one portion of that page, such as text, might present increased utility to a user over another such portion, e.g. graphics, of that same page. Specifically, if incremental benefit to the user, of pre-fetching, diminishes with each additional portion of a web page being prefetched, each such remaining portion need not be pre-fetched in favor of pre-fetching another page(s) or portion(s) thereof that is likely to provide increased incremental benefit to the user. The incremental benefit of any such portion would be measured by its corresponding flux-product (or discounted flux-product). Those page portions would be prefetched in order of their associated flux-products (or discounted flux-products). In some instances, portions of different web pages, given values of their respective flux-products (or discounted flux-products), may be successively prefetched in lieu of prefetching full pages. The incremental benefit of prefetching each such page or portion thereof can be adjusted downward to account for the cost(s) inherent with its prefetching.
BRIEF DESCRIPTION OF THE DRAWINGS
The teachings of the present invention can be readily understood by considering the following detailed description in conjunction with the accompanying drawings, in which:
FIG. 1 depicts a high-level block diagram of a typical networked Internet connection 5;
FIG. 2 depicts conventional CPU utilization diagram 100 and corresponding illustrative task chart 110, the latter showing task execution that could effectively utilize idle-time intervals shown in diagram 100;
FIG. 3A graphically depicts illustrative linearly-increasing expected value of computation (EVC) curves 310 for three different task instances;
FIG. 3B graphically depicts EVC flux, i.e. instantaneous time rate of change in EVC (dEVC/dt), curves 350 associated with curves 310 shown in FIG. 3A;
FIG. 4A graphically depicts non-linear EVC curve 410 for an illustrative task instance, along with, for purposes of comparison, constant EVC curve 430 for another task instance;
FIG. 4B graphically depicts approximate EVC flux curve 450 associated with curve 410 shown in FIG. 4A;
FIG. 4C graphically depicts illustrative non-linearly varying .phi..times.p curve 460 for a currently executing task instance and illustrative linearly varying discounted .phi..times.p curve 470 associated with a future task instance, along with corresponding time intervals and values thereat for comparing, on a successive time-slice basis, value of the currently executing task instance vs. discounted .phi..times.p of the future task instance;
FIG. 5 depicts a high-level block diagram of computer system (PC) 10 that implements one embodiment of my present invention;
FIG. 6 depicts a high-level block diagram of those portions of application programs 30, specifically web browser 35, that execute within client computer system (PC) 10 and collectively implement an illustration embodiment of my present invention;
FIG. 7 graphically depicts illustrative functions 710 and 720 that show utility, u, to a user as a complete web page is increasingly fetched and rendered;
FIG. 8 depicts Predefined Results Fetch Process 800 which is performed by browser 35 to implement a page-based URL retrieval strategy in accordance with my inventive teachings;
FIG. 9 graphically depicts illustrative function 910 that shows utility, u, to a user as discernible portions of a screenful of a web page, e.g. graphics and text, are each fetched and rendered in succession;
FIGS. 10A and 10B collectively depict a flowchart of Partial Page--Text before Graphics Fetch Process 1000 which is performed by browser 35 to implement a different retrieval URL retrieval strategy in accordance with my inventive teachings, i.e. fetching text first in favor of graphics from a common web page;
FIGS. 11A and 11B collectively depict a flowchart of Partial Page--Screenful Fetch Process 1100 which is performed by browser 35 to implement another retrieval URL retrieval strategy in accordance with my inventive teachings, i.e. fetching ordered screenfuls of content;
FIG. 12 graphically depicts illustrative function 1210 that shows utility, u, to a user as multiple graphical and textual portions of a common screenful for a web page are each fetched and rendered in succession;
FIGS. 13A and 13B collectively depict a flowchart of Partial Page--Screenful with Text before Graphics Fetch Process 1300 which is performed by browser 35 to implement yet another retrieval URL retrieval strategy in accordance with my inventive teachings, i.e. fetching text in favor of graphics from ordered screenfuls of content;
FIG. 14 graphically depicts empirically determined probability (expressed as a "hit fraction" and based on usage log data for a day), for a user then viewing a current web page on an MSNBC web site on that day, of a next successive page then selected by that user having been prefetched and stored in cache, as a function of a number of such pages that, based on transition probabilities across all such users, would then have been prefetched and stored in order of their likelihood of being accessed next;
FIG. 15A depicts illustrative display 1500 from a web browser, such as browser 35 shown in FIG. 6, that provides preview windows 1520 and collaborative filtering output 1530 for recommendations to a user;
FIG. 15B depicts abstraction 1550 of display 1500 that illustrates various transition probabilities associated with this display;
FIG. 16 depicts a high-level block diagram of those portions of application programs 80, specifically web server 85, that execute within server computer 60 shown in FIG. 1 and collectively implement another embodiment of my present invention;
FIGS. 17A, 17B, 17C collectively depict a flowchart of Future Page Fetch Process 1700 which is illustratively performed by browser 35 to prematurely terminate the fetch of, e.g., a current web page in favor of fetching a future web page where the expected refinement in the rate of change in utility (incremental utility) to the user in prefetching the future page is greater than the incremental utility associated with continuing to download the current page.
To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to the figures.
DETAILED DESCRIPTION
After considering the following description, those skilled in the art will clearly realize that the teachings of my present invention can be utilized in substantially any browser, whether it be for use with, e.g., an Internet, intra-net or other network environment, or even a non-networked environment. My invention is also applicable for use with substantially any information retrieval application to increase throughput, regardless of whether that application retrieves information from an external source, e.g. a networked file server or a locally situated dataset, such as a CD-ROM based dataset, or integrated into an operating system to examine local resources, e.g. files, on a computer. Essentially, the present invention relies on allocating, within a computer system, presently available computer resources, such as currently available processing capacity, to prefetching information, such as, e.g., files for web pages (or portions thereof), that is expected to provide the highest expected utility to a current user of that system. To further simplify this discussion, I will describe my invention in the context of its use in accessing web pages through an Internet connection.
FIG. 1 depicts a high-level block diagram of typical networked Internet connection 5. This connection is formed of client computer 10, here shown as illustratively a personal computer (PC), electrically connected in bi-directional fashion, through links 15 and 65, via network 50 (here the
Internet), to remote server computer 60. Web browser 35, typified by the Internet Explorer ("IE") version 4 browser (currently available from Microsoft Corporation of Redmond, Wash.), generally forms part of application programs 30 that are collectively stored within client computer 10 and locally executed. Web server 85, typified by the Internet Information Server (IIS) web server (which is also currently available from Microsoft Corporation), forms part of application programs 80 that are collectively stored and execute within server computer 60.
Once such a networked connection has been established between client computer 10 and server computer 60, a user stationed at the client computer can access a desired web page by supplying the browser with a corresponding web address (in the form of a uniform resource locator--URL) for that page. The term "page", in this context, refers to content accessed, via a URL, including, e.g., text, graphics and other information. The address can be supplied through any of various ways, which illustratively include: direct keyboard entry by the user; selection amongst a stored list of addresses, i.e. so-called "bookmarks"; or "clicking", such as through appropriate manipulation of a mouse, on an appropriate hot-link, for that address, then appearing on a browser control bar, or a home or other web page currently being displayed by the browser. In essence, once a user has supplied his(her) complete input to the browser, through whatever method the user chooses, the browser then sends appropriate commands, as symbolized by line 20, to server 60 to effectuate this user input, such as to retrieve a stored file for a web page for which the user has then supplied an address. In response, web server 85, executing within server computer
60, receives and processes these commands to download a corresponding file, oftentimes in hypertext markup language (HTML) source form, as symbolized by line 70, to the client computer. Upon receipt of this file, browser 35 appropriately processes the HTML source file to properly assemble and then render a web page, represented by this file, on a local display (not specifically shown in FIG. 1). The user, in turn, examines this page. Once the display is fully rendered or the user has instructed the browser to stop rendering the page via an explicit stop command or a click on a hotlink already rendered, the user can then enter a new web address, either using, e.g., any of the hot-links then appearing on the page, or through selection amongst the then stored bookmarks or direct keyboard entry. Accordingly, the user transitions among successive web pages during a common web session. Thus, by simply and successively pointing and "clicking" his(her) mouse at, e.g., an appropriate hot-link for each one of a number of desired web pages, the user can readily retrieve each desired page, typically a file, in succession from its corresponding web site and effortlessly jump from site to site, regardless of where those sites, e.g. such as that of server
60, are physically located.
Unfortunately, a conventional client computer often displays successive pages rather slowly--generally to the frustration of a user situated thereat.
In accordance with my invention, I have recognized that the speed at which web pages can be displayed (the term "rendered" also being synonymously used herein) can be significantly increased, on average, by harnessing available computer resources at a client computer, during periods of low processing activity when processing capacity would otherwise be wasted, such as during idle processing time, and network resources available during periods of low network activity, to prefetch and store web pages for subsequent access. The particular pages that are pre-fetched are determined through a user model as being those, given a page which a user is currently viewing or a sequence of pages visited, would provide the largest benefit, in terms of, e.g., expected utility, to that user. In that regard, the model provides a URL for each page in a set of pages and a corresponding estimate of the likelihood that, during a current session, a user will access each of those particular pages for viewing, e.g., transition to that page from a current page. While HTML source files are downloaded and processed by browser 35 for a particular web page, the browser partially renders the page with increasing amounts of content being made available for review by the user, until such time as all the required HTML source code files for that page have been fetched and processed by the browser--at which point the page is fully rendered. Hence, the term "rendering" specifically encompasses both partial and complete display of a web page.
Specifically, once a user, at a client computer, enters an address (e.g. a URL) of a desired web page, a set containing web addresses of pages, that based on the user model are each likely to be accessed in the future but during the current session or within a given time horizon by that user, are determined, with corresponding files therefor prefetched by the client computer either: (a) during intervals of low processing activity and/or low network activity, or (b) when the value of prefetching such pages that may be requested in the future exceeds that of continuing to download content from a page then being fetched. Once prefetched, the file for each page is stored in local cache at the client computer, such as computer 10, for ready access should the user next select that particular page. As successive web pages are selected by the user and displayed, the user model is updated through consideration of the current page; thereafter, new pages may be prefetched and so on. When limits are reached in local memory, based on memory allocated for prefetching, content cached through earlier prefetching can be over-written by files for a current set of prefetched pages, where the least valuable pages are targeted for replacement. Depending upon the specific user model used (such models being discussed in considerable detail below), a model can reside within browser 35 or within web server 85.
To facilitate reader understanding, I will first discuss typical atomistic processing that often occurs within a personal computer and which gives rise to intervals of low processing activity including idle time. I will then discuss how this idle time can be allocated in general to pre-computing available task instances, regardless of what those task instances are, in order to increase processing throughput. Next, I will discuss how precomputation can be done in the absence of intervals of low processing activity, namely by making computation or network resources available through reducing the allocation of such resources to a current task in favor of a potential future task. In this context, I will address two different scenarios. Since these scenarios and the underlying foundational concept of pre-computation are all independent of the particular application for which the task instances are executed or even the specific nature of the tasks themselves, for simplification, this discussion will purposely omit these aspects. These two scenarios involve pre-computing, during a current interval of time, a task instance, from a group of instances that are likely to be executed in the future, and which possess either of the following characteristics: (a) fixed utility values associated with the computation or transmission of a specific result, or (b) time-varying utility values associated with refining completeness of a result with ongoing computation or transmission of information over a network.
With that foundation in mind, I will then turn to discussing my present invention as to how precomputation can be used in a client computer, such as computer 10, in order to properly prefetch and store, during intervals of low processing and low network activity, such as idle time, web pages or portions thereof in order to significantly increase throughput of displayed pages. I will also discuss how my inventive teachings can apply even in situations where there is no idle time, by slowing or ceasing network activity associated with a current task and re-allocating the networking resources to the task of prefetching potential future information of interest. This particular discussion will address salient aspects of both hardware and software needed to implement my present invention.
A. Conventional Atomistic Task Processing
Conventional central processing unit (CPU) utilization, on an atomistic level, is often marked by short periods (e.g. bursts) of relatively high processing activity separated by periods, often longer, of relatively low processing activity, typically idle time. This phenomena is graphically depicted by curve 105 shown in diagram 100 of FIG. 2. This curve is typical of that generated for depicting real-time CPU utilization by a CPU usage history monitor feature selectable for display through a Task Manager process in the WINDOWS NT version 4 workstation operating system; this operating system is currently available from Microsoft Corporation of Redmond, Wash. (which also owns the registered trademark WINDOWS NT). Curve 100
illustratively contains three intervals of relatively high CPU activity, 105.sub.2, 105.sub.4 and 105.sub.6 (occurring during respective periods t.sub.2, t.sub.4 and t.sub.6) during which task instances A, B and C respectively execute. These intervals are separated by interspersed idle-time intervals 105.sub.1, 105.sub.3 and 105.sub.5 (also denoted as periods t.sub.1, t.sub.3 and t.sub.5, respectively). During each of these three idle-time intervals, a CPU is usually waiting for some other device, typically slower in speed than the CPU, to become available such that the CPU can resume its processing activity by utilizing that device, or data then available therefrom, in some fashion. The processing load that occurs during each of these idle-time intervals is relatively low, here depicted by illustratively 10% CPU utilization. In contrast, bursts 105.sub.2 and 105.sub.6, at least for part of their duration, fully utilize the CPU, i.e. to 100% of its processing capacity thereof; while burst
105.sub.4 illustratively does not.
Given the processing capacity that is available, but heretofore generally unused and thus wasted during each idle-time interval, increased system throughput could be had if a useful task(s) could be processed during each of these intervals.
B. Task Selection Algorithms for Yielding Optimal Resource Utilization
Advantageously, a task instance is selected at a beginning of each of these idle-time intervals and processed during the remainder of that interval. The selected instance is one that is most likely to occur in the near-future and will be precomputed, during an associated idle-time interval, to the extent of the remaining time available during that interval. Once this task instance has been precomputed, its results, partial if the task has not completed prior to the end of the interval, are stored for subsequent access and use. Ideally, by having these results precomputed and ready for future use, future response time, i.e. run-time delay, is appreciably shortened since that task instance, when it would otherwise be dispatched for execution, will have already executed--fully or at least partially. In this manner, available computer resources, here processing time, are maintained at relatively high usage during all time periods, rather than experiencing bursty usage patterns as conventionally occurs; hence, significantly enhancing overall system throughput.
In that regard, consider task chart 110, depicted in FIG. 2, which shows task execution that could illustratively occur to utilize idle-time intervals, such as those shown in diagram 100. Rather than merely waiting during each idle-time interval, the operating system, during the onset of that period, probabilistically analyzes future task instances to select a given task for precomputation. That instance is then processed to the extent of the available time remaining during that interval. For example, assume at the onset of idle-time interval 105.sub.1, a group of four unexecuted task instances I.sub.1, I.sub.2, I.sub.3 and I.sub.4 are likely to be invoked at some point in the near future. These tasks, viewed collectively, could be a portion of one or more application programs then executing, such as, e.g., a file save task, a file read task, a file download task, a format task or a spreadsheet rotate task.
Particularly in a personal computer processing environment, application based tasks are highly user dependent, in that each such task instance has an associated probability (likelihood) of being invoked by the user at a given time. For any such task instance, this probability accounts for a user not invoking that task at all and if the task is to be invoked, when, relative to a current time, that task is to be invoked. Those task instances with a higher probability are more likely to be invoked sooner than those tasks with a lower probability. Here, illustrative task instances I.sub.1, I.sub.2, I.sub.3 and I.sub.4 correspondingly carry, as symbolized by lines 122, 124, 126 and 128 corresponding probabilities p.sub.1, p.sub.2, p.sub.3
and p.sub.4 of future execution. Ignore for the moment just how these probabilities are determined; that will be shortly addressed below through two different scenarios. For the four available task instances and at the onset of idle-time interval t.sub.1, operation 120 compares the corresponding four probability measures and selects that task instance, here I.sub.2, then having the highest probability, p.sub.2, of future execution. Once this task is selected, the operating system then executes this task, as symbolized by block 130, throughout the remainder of this idle-time interval.
Enhanced performance and throughput results if the selected task is executed to the fullest extent of the available time during this idle-time interval rather than being prematurely terminated in favor of another task. Use of a conventional time-sharing approach, under which an equal amount of time is allocated to each task instance in a group, would likely result in a sub-optimal allocation of available processing time.
Should idle-time interval t.sub.1 elapse prior to completion of task instance I.sub.2, this instance then halts, with partial results stored in memory, in favor of task instances A being executed, as symbolized by block 135, during the following high activity period, i.e. burst 105.sub.2. Similarly, at the onset of the next idle-time interval t.sub.3, the operating system will select, as symbolized by operation 140, a task instance, from those future task instances then available, which has the highest probability associated with these instances, here illustratively task instance I.sub.7 from a group then consisting of illustratively task instances I.sub.5, I.sub.6, I.sub.7 and I.sub.8 carrying associated probability measures p.sub.5, p.sub.6, p.sub.7 and p.sub.8, as symbolized by lines 142, 144, 146 and 148, respectively. Task instance I.sub.7 then executes, as symbolized by block 150, to the extent of the available time remaining during idle-time interval t.sub.3. Based on the probabilities of all future task instances, the task instance, here interval I.sub.7, that is executed during an idle-time interval may not necessarily be the task instance, e.g. instance I.sub.2, that was only partially executed during the most recent idle-time interval. Immediately thereafter during high activity period t.sub.4 (burst 105.sub.4), task instances B execute, as symbolized by block 160.
If, however, sufficient time remains during any such idle-time interval, then another probabilistic based assessment is made to select a future task instance from among those then available for precomputation and that particular task instance is executed to the extent of the remaining time, and so forth until that interval elapses. In that regard, at the onset of idle-time interval t.sub.5, operation 170 assesses probability measures, p.sub.9, p.sub.10 and p.sub.11 carried, as represented by lines 172, 174 and 176, by a group of future task instances I.sub.9, I.sub.10 and I.sub.11, respectively. The task instance in this group then having the highest measure, here illustratively task instance I.sub.10, then executes, as symbolized by block
180. Since this task instance completes prior to the end of idle-time interval t.sub.5, probability measures, p.sub.12 and p.sub.13, of a group of future task instances, then available for precomputation, here containing task instances I.sub.12 and I.sub.13, are assessed, as symbolized by operation 190, with one of these tasks having the then highest measure, here instance I.sub.13, being selected. As symbolized by block 200, this instance then executes to the extent of the remaining time left in this idle-time interval. At the conclusion of idle-time interval t.sub.6, task instances C execute during ensuing high activity period t.sub.6 (burst 105.sub.6), as symbolized by block 210, and so forth.
As noted above, two different scenarios (characteristics) can arise during which task instances can be properly selected for precomputation during idle-time or other periods of low processing activity: those future task
instances that are worth some specific amount of, e.g., constant, value over time, following the completion of the current task and those future task instances that exhibit time-varying value with ongoing refinement or transmission of a partial result. Though individually any task instance within a group of future task instances can exhibit either of these two value-based characteristics, for simplicity, I will separately address each of these characteristics and the decisional analysis used to select a future task instance from among a group of such instances having the same characteristic. Inasmuch as those skilled in the art will surely realize that the analysis, regardless of the modality used, reduces to a probability-based measure, these different modalities, depending upon the characteristics of the tasks in a given group, can be combined as needed during the onset of any idle-time interval to select an appropriate task instance, presently executing or future, from amongst those in the group, for current or continued execution, respectively.
1. Task Instances Exhibiting Constant Value Over Time
Some task instances provide a fixed value (utility) with their completion that does not vary with time. The value may be known quantitatively or at least qualitatively. The value can be used to prioritize operations. For example, in a database application, a file save operation takes precedence over exiting the database program or even changing a existing entry or creating a new record if the database is open; the simple reason being to preserve the current data then resident in the database. Other tasks, such as changing a background color of a display, would clearly be of much lesser importance. As such, certain tasks can be ranked in terms of their future importance, which may include, e.g., their fixed value, their future costs, such as for delayed future availability of results from those tasks, or at least qualitative importance to a user. Task instances that possess a higher future importance, e.g., value, quantitatively or qualitatively, would simply be ranked ahead of those exhibiting lesser importance.
Within a given group of future task instances available at the onset of an idle-time interval wherein each of these instances possesses either a fixed value or qualitative ranking in terms of its importance vis-a-vis other such task instances, the task instance that then possesses the highest value or importance (quantitatively or qualitatively) would be selected and executed first during that interval--that instance is the one then providing the highest current utility. That instance would then be removed from further consideration. The remaining future task instances in a group would be re-evaluated at the onset of each successive idle-time interval to select the next task instance, from the group as it then exists, which would then be most appropriate for precomputation. Should additional time remain during any such interval, then the future task instances then existing would re-evaluated for possible precomputation during the remainder of that interval. Should the ranking reveal two (or more) task instances that then possess the same highest equal value or importance, then any of these particular task instances could be selected, on an indifferent basis, and be subjected to any portion of the available time for precomputation during an associated idle-time interval. The time available could be applied to any of the tasks in any proportion until all of the tasks are completed or this time becomes unavailable or ceases.
Specifically, expected delay at run-time associated with, e.g., precomputing a task instance is a function of the actions the system takes to precompute answers to challenges faced by that instance and the duration of an idle-time interval during which such precomputation is to occur. Here, a goal is to minimize run-time delay.
Time parameter, t(I.sub.i), represents time required to completely solve task instance I.sub.i. Parameter T represents total time available during an idle-time interval with t.sub.i.sup.f representing a fraction of available idle-time allocated to precomputing instance I.sub.i ahead of time. The total usable idle time T is less than or equal to the maximal exploitable idle time, T.sub.m, during any one idle-time interval and sufficient to execute all potential future task instances, which is given by equation (1) as follows: ##EQU1## With these terms defined as such, the expected run-time delay before completing execution of a future task instance is given by expression (2) as follows: ##EQU2## E represents observed evidence, i.e., for example, the current status of: task instances, the processing and application environments, and other pertinent characteristics.
Expected savings gained from idle-time computation can be viewed as set forth in expression (3): ##EQU3## For the next period of constant idle-time, T, the expected savings can be expressed in expression (4) as: ##EQU4## Hence, these savings will be optimized by maximizing the quantity ##EQU5##
Thus, from this, given an ordering of future task instances with conditional probabilities, p(I.sub.1 .vertline.E)>p(I.sub.2 .vertline.E)> . . . p(I.sub.n .vertline.E), representing the likelihood that the corresponding instance will be executed during the next idle-time interval, the idle-time fraction that minimizes expected computation time, i.e. run-time delay, in that next period is to apply available computation time to the most likely future task instance until it is completely solved, then the next most likely future task instance and so on until the cessation of the available idle-time or all potential future task instances have been executed in that period, whichever comes first. Moreover, if two or more of these future task instances possess equally valued likelihoods, the expected computation time in the next period, i.e. run-time delay, is minimized by partitioning resources, here available processing time, in that period to the equally likely instances in any configuration of fractions. Hence, for all such equally likely task instances, any one of them can be selected, on an indifferent basis, for computation during that interval without adverse effect on expected run-time savings.
In general, application response time, in terms of expected run-time delay, can be advantageously reduced by selecting the future task instance(s), that has the highest importance, in terms of its likelihood of occurrence, for precomputation during an idle-time interval.
In many settings, the cost of waiting for a computational result depends on context-dependent time criticality. Let me generalize the results on minimizing expected delay to minimizing an expected cost of delay. The generalization is based on an analysis similar to the one used herein to identify policies for minimizing delay. Assume that each future problem instance has a time-dependent cost function, Cost (I.sub.i,t), that takes as arguments, an instance and the time delay required to compute that instance following a problem-challenge. Beyond specifying time criticality as a function of the instance, a distinct context variable can be employed. Without precomputation, the expected cost of waiting for a r