CACHE AND INDEX REFRESHING STRATEGIES FOR VARIABLY DYNAMIC ITEMS AND ACCESSES

• US 20100332513A1
• Filed: 06/26/2009
• Published: 12/30/2010
• Est. Priority Date: 06/26/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shahaf, Dafna, Lubetzky, Eyal, Azar, Joseph Yossi, Horvitz, Eric
• Granted Patent: US 9,213,780 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

Many computing scenarios involve an item cache or index, comprising items corresponding to source items that may change without notice, rendering the item in the item cache or index stale. It may not be possible to guarantee the freshness of the items, but it may be desirable to reduce staleness in an efficient manner. Therefore, the refreshing of items may be prioritized by first predicting the query frequency of respective item representing the rate at which an item is retrieved from the item cache (e.g., by monitoring queries for the item), predicting an update frequency representing the rate at which the source item is updated by the source item host (e.g., by classifying the source item type), and computing a refresh utility representing the improvement in cache freshness achieved by refreshing the item. Respective items may then be prioritized for refreshing according to the computed refresh utilities.

Claims

1. A method of prioritizing a refreshing of items provided in response to queries, the items stored in an item cache by a computer having a processor, respective items corresponding to a source item retrieved from a source item host accessible to the computer, and the method comprising:

executing on the processor instructions configured to;

for respective items;

predict a query frequency of queries requesting the item,

predict an update frequency of the source item by the source item host, and

compute a refresh utility of the item based on the query frequency and the update frequency; and

prioritize the refreshing of the items based on the refresh utilities.

2. The method of claim 1:

the source items comprising web-accessible source items;

the source item hosts comprising webservers hosting the web-accessible source items; and

the item cache comprising a proxy cache configured to;

cache web-accessible source items that are frequently requested by the users, and

provide an item corresponding to a web-accessible source item requested by a user.

3. The method of claim 1:

the source items comprising web-accessible source items;

the source item hosts comprising webservers hosting the web-accessible source items; and

the item cache comprising a web search cache configured to identify web-accessible source items corresponding to web queries received from web users.

4. The method of claim 1, predicting the query frequency comprising:

for respective items;

tracking a rate of queries for the item, and

computing a query frequency for the item based on the rate of queries;

generating an item query frequency set configured to map items to query frequencies; and

predicting the query frequency of an item comprising;

selecting the query frequency of the item from the item query frequency set.

5. The method of claim 1, predicting the query frequency of the item comprising:

training a probabilistic classifier to predict query frequencies of items based on a training item set comprising items associated with known query frequencies, and

applying the probabilistic classifier to an item to predict the query frequency of the item.

6. The method of claim 1, predicting the update frequency of a source item by the source item host comprising:

extracting at least one source item criterion of the source item;

classifying the source item as a source item type according to the at least one source item criterion; and

predicting the update frequency of the source item based on the update frequencies of other source items of the source item type.

7. The method of claim 6, generating the update frequency set comprising:

generating a machine learning function configured to map source item types to update frequencies, and

training the machine learning function based on a training data set associating source items of respective source item types with update frequencies.

8. The method of claim 1, computing the refresh utility comprising:

for respective items;

computing a refresh probability for the item based on the query frequency of queries requesting the item and the update probability of the source item by the source item host, the refresh probabilities selected to yield a desirably high refresh utility; and

after at least one item in the item cache is refreshed, recomputing the refresh probability for the item based on the query frequency of queries requesting the item and the update probability of the source item by the source item host.

9. The method of claim 8, the refresh utility computed according to a refresh utility model comprising:

maxΣ

_t=1^T(Σ

_i=1ⁿx_tⁱ·

u_i)

such that;

Σ

_pi≦

1

p_i≧

0

0≦

x_tⁱ≦

1

x₀ⁱ=0

x_t+1ⁱ=x_tⁱ·

(1−

c_i)·

(1−

p_i)+p_i

wherein;

n represents the number of items in the item cache;

t represents a time point;

u_i represents a query frequency of item i;

x_tⁱ represents a probability that source item i has been updated by the source item host at time t since the item was last refreshed;

c_i represents a freshness probability comprising a probability that the source item i has not been updated by the source item host of source item i since the item i was last refreshed; and

p_i represents a refresh probability of item i at time t.

10. The method of claim 9, computing the refresh probabilities for respective items comprising:

selecting an item subset comprising at least one item from the item cache;

computing a Lagrange multiplier over respective items of the subset based on the query frequency of queries requesting the item and the update probability of the source item by the source item host; and

for respective items, computing a refresh probability based on the update frequency of the source item by the source item host, the query frequency of queries requesting the item, and the Lagrange multiplier.

11. The method of claim 9, computing the refresh probabilities for respective items comprising:

forming an item subset comprising the items of the item cache;

while at least one item in the item subset may comprise a refresh probability less than zero;

removing items from the subset having a refresh probability less than zero;

computing a Lagrange multiplier over respective items of the subset based on the query frequency of queries requesting the item and the update probability of the source item by the source item host; and

for respective items in the item subset, computing a refresh probability.

12. The method of claim 11:

the method comprising;

computing an output of an objective function according to the mathematical formula;

13. The method of claim 9, computing the refresh probabilities for respective items comprising:

iteratively allocating a refresh probability increment to the refresh probability of the item having a maximum derivative flux based on the query frequency, the update frequency, and the refresh probability allocated to the item.

14. The method of claim 1, the instructions configured to, for respective items:

select a refresh frequency based on the refresh utility, and

refresh the item stored in the item cache according to the refresh frequency of the item.

15. The method of claim 14:

the computer comprising a cache refreshing resource set comprising at least one cache refreshing resource configured to refresh items in the item cache, and

the prioritizing comprising;

allocating the cache refreshing resources of the cache refreshing resource set to refresh items in the item cache based on respective refresh utilities of the items.

16. The method of claim 15, the instructions configured to compute an aggregate refresh utility of the items stored in the item cache that is achievable by the cache refreshing resource set.

17. The method of claim 16, the instructions configured to:

compute a first aggregate refresh utility of the items stored in the item cache that is achievable by a first cache refreshing resource set;

compute a second aggregate refresh utility of the items stored in the item cache that is achievable by a second cache refreshing resource set; and

compute a differential aggregate refresh utility of the items stored in the item cache that is differentially achievable by the first cache refreshing resource set as compared with the second cache refreshing resource set.

18. The method of claim 1, the instructions configured to:

compute a query quality metric of the item cache indicating a quality of at least one query result generated in response to a query applied to the item cache, and

prioritize the refreshing of the items based on the refresh utilities in order to improve the query quality metric of the item cache.

19. A system configured to prioritize a refreshing of items provided in response to queries, the items stored in an item cache by a computer having a processor, respective items corresponding to a source item retrieved from a source item host accessible to the computer, and the system comprising:

a refresh utility computing component configured to compute a refresh utility of the items stored in the item cache by, for respective items;

predicting a query frequency of queries requesting the item,

predicting an update frequency of the source item by the source item host, and

computing a refresh utility of the item based on the query frequency and the update frequency; and

an item prioritizing component configured to prioritize the refreshing of the items based on the refresh utilities.

20. A computer-readable storage medium comprising processor-executable instructions, the instructions configured to, when executed by a processor of a computer comprising an item cache of items and at least one cache refreshing resource configured to refresh items in the item cache, respective items provided in response to queries and corresponding to a source item retrieved from a source item host accessible to the computer, refresh respective items stored in the item cache by:

predicting a query frequency of queries requesting the item by;

tracking a rate of queries for the item,

computing a query frequency for the item based on the rate of queries, and

generating an item query frequency set configured to map items to query frequencies;

selecting the query frequency of the item from the item query frequency set;

predicting an update frequency of the source item by the source item host by;

generating an update frequency set identifying update frequencies of source items of respective source item types by;

generating a machine learning function configured to map source item types to update frequencies, and

training the machine learning function based on a training data set associating source items of respective source item types with update frequencies

extracting at least one source item criterion of the source item;

classifying the source item as a source item type according to the at least one source item criterion; and

predicting the update frequency of the source item based on the update frequencies of source items of the source item type; and

identifying from the update frequency set the update frequency of the source item type of the source item;

computing a refresh utility of the item based on the query frequency and the update frequency by;

computing a refresh probability for the item based on the query frequency of queries requesting the item and the update probability of the source item by the source item host, the refresh probabilities selected to yield a desirably high refresh utility; and

after at least one item in the item cache is refreshed, recomputing the refresh probability for the item based on the query frequency of queries requesting the item and the update probability of the source item by the source item host;

prioritizing the refreshing of the items based on the refresh utilities; and

refreshing the items in the item cache according to the refresh frequency of the item by allocating the cache refreshing resources of the cache refreshing resource set to refresh items in the item cache based on respective refresh utilities of the items.