System and method for caching

• US 6,415,368 B1
• Filed: 12/22/1999
• Issued: 07/02/2002
• 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., Glance, Natalie S., Pitkow, James
• Primary Examiner(s): Hudspeth, David
• Assistant Examiner(s): TZENG, FRED
• Application Number:
  US09/470,126
• Time in Patent Office: 923 Days
• Field of Search: 711/156, 711/122, 711/158, 711/118, 711/151, 709/213, 707/2, 707/10, 705/1, 705/26
• 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. The caching method may also be used to improve performance of a recommender system.

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 value data comprises a measure of the relative quality or value attributes of the item;

associating the value data with the item;

wherein the items comprise web sites and wherein the value data comprises a weighted combination of statistical information pertaining to the number of unique users visiting the web site and recommendation data from a recommender system which provides a value for an item according to user recommendations of the web site;

prioritizing the items to be stored in the cache in accordance with the relative value of each item; and

storing those items having the highest value in the cache.

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

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

4. 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.

5. The method of claim 1, further comprising:

obtaining recency 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 of use data.

6. 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.

7. The method of claim 1, wherein the prioritizing step comprises evaluating w(t_i), the weighting metric, $\begin{array}{c}w\end{array}$

(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<sub>i−

1</sub> 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 ƒ

(v_i) is a monotonically increasing function of the value; and

storing those items having the greatest weight in the cache.

8. The method of claim 1, wherein the items comprise web pages and wherein the value data comprises a weighted combination of statistical information pertaining to the number of unique users visiting a web site associated with the web pages and recommendation data from a recommender system which provides a value for an item according to user recommendations of the web page.

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 value data for items retrieved from the network, wherein each retrieved item is associated with user-dependent value data comprising a measure of the relative quality or value attributes of the item;

wherein the items comprise web sites and wherein the value module provides value data comprising a weighted combination of statistical information pertaining to the number of unique users visiting the web site and recommendation data from a recommender system which provides a value for an item according to user recommendations of the web site;

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; and

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

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

11. The system of claim 9 wherein the value module further provides value data including recency and frequency of web site access data.

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 further obtains recency and frequency of use data for each item and prioritizes 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.

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

$\begin{array}{c}w<br><br>\left(t_i\right)=\frac{1}{{\mathrm{MTNR}}_i},\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}\\ {\mathrm{\alpha <br><br>}}^{\mathrm{\prime <br><br>}}=\frac{\mathrm{\alpha <br><br>}}{f<br><br>\left(v_i\right)},{\mathrm{MTNR}}_i\end{array}$

is the mean time to the next request for item i, t_i is the time since the last reference, MTNR<sub>i−

1</sub> 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 ƒ

(v_i) is a monotonically increasing function of the value; and

stores those items having the greatest weight in the cache.

16. 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.

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

18. The system of claim 9, wherein the computer comprises a recommender system.