Utility-based archiving

• US 7,043,506 B1
• Filed: 06/28/2001
• Issued: 05/09/2006
• Est. Priority Date: 06/28/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric J.
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): GODDARD, BRIAN D
• Application Number:
  US09/894,392
• Time in Patent Office: 1,776 Days
• Field of Search: 707/2, 707/10, 707/200, 707/204, 709/206, 709/207
• US Class Current: 707/661
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A system and associated methodology is provided that is adapted to infer what to do with an item, and more particularly whether to archive and/or keep active an item in a more active, easy-to-access store based upon a cost-benefit analysis. The cost-benefit analysis determines the overhead associated with keeping the item active (e.g., not archiving it) versus the gains in connection with having quick and easy access to the item. The cost of maintaining an item in an active state is measured in terms of the size of the item which, in turn, affects the amount of space needed to store it. The benefit of keeping the item active is measured in terms of a probabilistic determination describing how a user will access the item in the future, which is a reflection of the utility of the item in an accessible state. The invention leverages notions of temporal sensitivity of the likelihood that an item will be needed in the future such that determined values and inferences can be dynamically updated over time. Items having a small probability of being accessed again after an initial review are categorized as one-shot items.

Claims

1. A system that facilitates maintaining an item, comprising:

a first data store that stores the item in an active state;

a second data store that stores the item in an archived state; and

an inference system that inferentially determines whether to store the item in an active or archived state based at least in part upon information related to at least one of;

a property of the item, a property of a user and extrinsic data, wherein the system stores the item in an archived state after a first access if the inference system determines that the user is likely to access the item only once.

2. The system of claim 1 further comprising:

a property log that stores user preferences gathered from implicit evidence obtained by monitoring user activity, the inference system consulting the property log when making an inferential determination.

3. The system of claim 1, the inference system utilizing a value density of the item to determine whether to store the item in an active or archived state.

4. The system of claim 3 wherein the value density can be stated as the probability of user access given evidence divided by the size of the item and which can be defined as:

$\mathrm{value}<br><br><br><br>\mathrm{density}=\frac{p<br><br>\left(\mathrm{access}❘<br><br>E\right)}{\mathrm{item}<br><br><br><br>\mathrm{size}}$

5. The system of claim 1 further comprising:

a learning system that acts upon the inference system and modifies inferences made thereby based upon at least one of;

a property of the item, a property of a user, extrinsic data, a determined probability and a value density.

6. A utility based item archiving system comprising:

means for storing an item in fast memory or archival memory, the archival memory being slower than the fast memory;

means for determining one or more costs associated with storing the item in fast memory, at least one cost relating to the size of the item;

means for determining one or more gains associated with storing the item in fast memory, at least one gain relating to the utility of the item; and

means for inferring whether to store the item as active in fast memory or to archive the item in archival memory based upon size of the fast memory, the one or more costs, the one or more gains, and whether the item is a one-shot item.

7. The system of claim 6 being temporally sensitive such that the determined utility of the item and storage inferences drawn therefrom are continually updated over time.

8. The system of claim 7 wherein the means for inferring determines a value density that is a measure of item utility versus size.

9. The system of claim 8 wherein the means for inferring employs a knapsack packing analysis to determine how to store the item.

10. The system of claim 9 wherein, when more than one item exists, the knapsack packing analysis considers respective value densities of items to determine which items to store as active and which items to archive.

11. A method for determining how to store items comprising:

determining respective item utilities through probabilistic computations;

determining respective value densities of the items based upon determined probabilities of future item access and item size;

inferring whether to store actively, archive or discard items based upon the determined probabilities, value densities and whether the items are likely to be accessed only once.

12. The method of claim 11 further comprising:

updating determined item utilities over time;

determining modern value densities based upon updated item utilities; and

making contemporary inferences from at least one of;

the temporally adjusted probabilities and value densities.

13. The method of claim 12 further comprising:

mitigating inefficient use of active space by applying a knapsack computation to the modern item value densities.

14. A method of streamlining actively stored items comprising:

determining item utilities and value densities;

ordering items according to their utilities and value densities;

storing items in an active item store having fast memory according to their utilities and value densities as space permits;

removing one or more items from the active item store to make space available for an item with a higher utility and value density, wherein removing the one or more items comprises archiving the items in a slower data store when at least one of;

determined item utilities and value densities fall below a predetermined threshold; and

removing one-shot items from the active item store after the one-shot items are accessed a first time.

15. A computer-readable medium storing computer-executable instructions for performing the method of claim 14.

16. A system to infer how to store an item, comprising:

a probability component to determine a probability that the item will be accessed at a later time;

a cost-benefit component to determine a value density of the item as a function of the determined probability and size of the item; and

an inference system to infer whether to store the item in an active fast memory or archive the item in a slower store based upon the determined value density, space available in the fast memory and value density of at least one other item, wherein the system archives the item after a first access if the inference system infers that the item will be accessed only once.

17. The system of claim 16 wherein the probability component determines the probability based upon at least one of:

information related to a property of the item, a property of a user and extrinsic data.

18. The system of claim 17 further comprising:

a property log to store information regarding at least one of;

a property of the item, a property of the user and extrinsic data.

19. The system of claim 18 being temporally sensitive such that information stored in the property log is updated over time.

20. The system of claim 19 being temporally sensitive such that at least one of:

the determined probability, value density and inferences drawn therefrom are updated over time.

21. The system of claim 20 further comprising:

a learning system to learn how to adjust the inference system based upon at least one of;

updated log information, determined probabilities and value densities.

22. The system of claim 16 further comprising:

an interactive user interface (UI).

23. The system of claim 22 wherein conditions are utilized by the probability component and inference system, the UI including a selection element to allow a condition to be enabled/disabled.

24. The system of claim 23 wherein the UI further comprises an entry element to allow a condition to be configured.

25. A system to determine which of a plurality of items to store actively comprising:

a probability component to determine respective probabilities that the plurality of items subsequently will be accessed;

a cost-benefit component to determine respective value densities as a function of the respective probabilities and sizes of the plurality of items;

an inference system to infer whether the plurality of items should be actively stored in fast memory based upon the respective value densities; and

an optimization component to determine which of the plurality of items to remove from being actively stored and place in an archival store based upon a comparison of relative value densities of the items, an amount of active space available and whether the items are likely to be accessed more than once.

26. The system of claim 25 wherein the probability component determines the respective probabilities of the plurality of items based upon at least one of:

respective properties of the items, a property of a user and extrinsic data.

27. The system of claim 26 further comprising:

a property log operative to store information regarding at least one of respective properties of the plurality of items, a property of the user and extrinsic data.

28. The system of claim 27 being temporally sensitive such that information stored in the property log is updated over time.

29. The system of claim 28 being temporally sensitive such that at least one of determined probabilities, value densities and inferences drawn therefrom are updated over time.

30. The system of claim 29 further comprising:

a learning system to learn how to adjust the inference system based upon at least one of;

updated log information, determined probabilities and value densities.

31. A method to determine which of a plurality of items to store actively comprising:

determining respective probabilities that the plurality of items will be accessed in the future;

determining respective value densities as a function of the respective probabilities and sizes of the plurality of items;

ordering the plurality of items according to their value densities;

inferring whether the plurality of items should be actively stored in fast memory based upon at least one of;

respective probabilities and value densities;

determining which of the plurality of items to store in active space based upon the order of the value densities and an amount of active space available; and

determining which of the plurality of items to remove from active space based upon the order of the value densities and the amount of active space available, and wherein items that are likely to be accessed only once are removed from active space after they are accessed once.

32. The method of claim 31 further comprising:

determining the respective probabilities based upon at least one of;

respective properties of the items, a property of a user and extrinsic data.

33. A computer-readable medium storing computer-executable instructions for performing the method of claim 31.

34. A system to infer whether an item will be accessed only once or more than once comprising:

an inference system to infer whether an item will be accessed only once or more than once and to discard or move one or more items likely to be accessed only once to a slower memory store after the one or more items are accessed once, the inference based on a comparison of properties of the item to properties of other items that have been accessed only once, the inference system analyzing properties of a user and extrinsic data;

the inference system having;

a probability component to determine the probability that the item will be accessed only once; and

a cost-benefit component to determine a value density of the item as a function of the determined probability, the inference system comparing at least one of;

the determined probability and value density to probabilities and value densities of items that have been accessed only once to infer whether the item is likely to be accessed only once.

35. A method to infer whether an item will be accessed once or more than once comprising:

comparing properties of the item to properties of other items that have been accessed once;

analyzing properties of a user and extrinsic data;

determining a probability that the item will be accessed only once;

determining a value density of the item as a function of the determined probability and size of the item;

comparing the determined probability and value density to probabilities and value densities of items that have been accessed once; and

removing the item from fast memory after the item has been accessed if at least one of the determined probability and value density of the item are similar to at least one of probabilities and value densities of other items that have been accessed once.

36. A computer-readable medium storing computer-executable instructions for performing the method of claim 35.

37. An interactive user interface (UI) to display a condition that affects how a decision is made regarding the storage of an item comprising:

a selection element to allow a condition to be enabled/disabled; and

an entry element to permit a condition to be configured, wherein the condition relates to a probabilistic analysis for determining whether to store the item in a fast memory or in an archival memory, the probabilistic analysis based at least in part on the item'"'"'s worth relative to other items to be stored and size of the fast memory and wherein the item'"'"'s worth is determined at least in part by calculating a probability a user will access the item at some later time, the item'"'"'s worth being dependent at least in part on whether the item is a one-shot item.