System and method for caching

• US 6,631,451 B2
• Filed: 04/22/2002
• Issued: 10/07/2003
• Est. Priority Date: 12/22/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Adamic, Lada A., Huberman, Bernardo A., Pitkow, James, Glance, Natalie S.
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): Peugh, Brian R.
• Application Number:
  US10/128,011
• Publication Number:
  US 20020147895A1
• Time in Patent Office: 533 Days
• Field of Search: 711/133, 711/134, 711/130, 711/147, 711/159, 711/158, 711/151
• US Class Current: 711/158
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

A system and method of caching uses quality or value attributes, provided for example, by a recommender system or by a dynamical analysis of site accesses, which are attached to cached information to prioritize items in the cache. Documents are prioritized in the cache according to the relative value of their content. Value data may be provided from a recommender system which provides a value for a document according to user recommendations (using explicit recommendations) or from statistical analysis of site visits from unique users (implicit recommendations) or a combination of the two to identify the higher value documents.

Claims

1. A method for determining which items to store in a cache, comprising:

obtaining user-dependent value data for each item to be stored in the cache, wherein user-dependent value data comprises a measure of the relative quality or value attributes of the item to a particular user;

associating the value data with the item;

prioritizing the items to be stored in the cache in accordance with the relative value of each item, wherein relative value is based upon the number of unique users providing user-dependent value data for each item; and

storing those items having the highest value in the cache.

2. The method of claim 1, wherein the value data comprises recommendation data from a recommender system which provides a value for an item according to user recommendations.

3. The method of claim 2, wherein recommendation data is a function of the quality and the quantity of recommendations from users of the item.

4. The method of claim 1, wherein the items comprise web sites and wherein the value data comprises the number of unique users visiting the web site.

5. The method of claim 1 wherein the value data further includes recency and frequency of web site access data.

6. The method of claim 1 further comprising, for each item stored in the cache, validating the item'"'"'s value data and reprioritizing the items stored based on the validated value data.

7. The method of claim 1, further comprising:

obtaining recency and frequency of use data for each item; and

prioritizing the items to be stored in the cache in accordance with the relative value of each item and each item'"'"'s recency and frequency of use.

8. The method of claim 1, wherein the prioritizing step comprises evaluating w(ti), the weighting metric, $w$

(ti)=1MTNRi, 



where

 



MTNRi=α

′



ti+(1-α

′

)

MTNRi-1

 



and

 



α

′

=α

f

(vi),MTNRi

 

is the mean time to the next request for item i, t_i is the time since the last reference, MTNR_i-l is the previous value, α

′

is the exponential damping coefficient, v_i is the value or utility of item i as provided by a recommender system, and f(v_i) is a monotonically to increasing function of the value; and

storing those items having the greatest weight in the cache.

9. A system for caching items on a distributed network, comprising:

a computer for storing and for retrieving items from the network, wherein the computer includes a processor and a cache for storing items retrieved from the network, wherein the processor, responsive to a request for a particular item, determines if the item is stored in the cache and if not, retrieves the item from the network; and

a value module for providing user-dependent value data for items retrieved from the network, wherein user-dependent value data comprises a measure of the relative quality or value attributes of the item to a particular user;

wherein the processor, for each retrieved item, responsive to the retrieved item'"'"'s value data, prioritizes the retrieved item and any items stored in the cache in accordance with the relative value data of each item, wherein relative value is based upon the number of unique users providing user-dependent value data for each item; and

stores those items having the highest value data in the cache.

10. The system of claim 9, wherein the value module further comprises a recommender system for providing a value data for an item according to user recommendations.

11. The system of claim 10, wherein the recommender system provides recommendation data as a function of the quality and the quantity of recommendations from users of the item.

12. The system of claim 9, wherein the processor, for each item stored in the cache, validates the item'"'"'s value data and reprioritizes the items stored based on the validated value data.

13. The system of claim 9, wherein the processor further obtains recency of use data for each item;

and priorities the items to be stored in the cache in accordance with the relative value of each item and each item'"'"'s recency of use data.

14. The system of claim 9, wherein the processor priorities the items in accordance with an evaluation of w(ti), the weighting metric:

$w<br><br>\left(t_i\right)=\frac{1}{{\mathrm{MTNR}}_i},\text{\hspace{1em}<br><br>}<br><br>\mathrm{where}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{MTNR}}_i={\mathrm{\alpha <br><br>}}^{\mathrm{\prime <br><br>}}<br><br>t_i+\left(1-{\mathrm{\alpha <br><br>}}^{\mathrm{\prime <br><br>}}\right)<br><br>{\mathrm{MTNR}}_{i-1}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\alpha <br><br>}}^{\mathrm{\prime <br><br>}}=\frac{\mathrm{\alpha <br><br>}}{f<br><br>\left(v_i\right)},{\mathrm{MTNR}}_i<br><br>\text{\hspace{1em}<br><br>}$

is the mean time to the next request for item i, t_i is the time since the last reference, MTNR_i-l is the previous value, α

′

is the exponential damping coefficient, v_i is the value or utility of item i as provided by a recommender system, and f(v_i) is a monotonically increasing function of the value; and

stores those items having the greatest weight in the cache.

15. The system of claim 9, wherein the value data comprises positive, negative and zero values and wherein an item receives a value data of zero if no value data is available for it.

16. The system of claim 9, wherein the computer comprises a network proxy server.