Exponential decay set pruning

Patent metadata

Field	Value
Publication number	US-9569452-B1
Application number	US-201213611475-A
Country	US
Kind code	B1
Filing date	Sep 12, 2012
Priority date	Sep 12, 2012
Publication date	Feb 14, 2017
Grant date	Feb 14, 2017

Abstract

Disclosed are various embodiments for applying a pruning to data sets, files, logs, and/or any other information. A binning methodology may be employed to determine which data to retain or discard to determine a resulting set of data resembling an exponential decay where more recent items of data are more likely to be retained and more archaic items of data are more likely to be discarded. The resulting set of data may be associated with an average age.

First claim

Therefore, the following is claimed:

1. A non-transitory computer-readable medium embodying program code executable in at least one computing device that, when executed, causes the at least one computing device to:
perform a prune of a plurality of files residing in a memory device such that a plot of an average age of the plurality of files retained after the prune fits an exponential decay curve and the average age of the plurality of files matches a desired average age, by:
approximating, for a first one of the plurality of files, a count of the plurality of files having a timestamp more recent than an age of the first one of the plurality of files;
identifying a first index and a second index associated with a potential storage location in the memory device for the first one of the plurality of files based at least in part on the count; and
applying a binning function that causes a first portion of the plurality of files to be deleted and a second portion of the plurality of files to be retained, wherein the binning function comprises determining whether to replace a second one of the plurality of files residing in the potential storage location in the memory device associated with the first index or the second index with the first one of the plurality of files by comparing the age of the first one of the plurality of files to an age of the second one of the plurality of files residing in the potential storage location;

transmit a notification to a second computing device comprising information associated with the plurality of files retained after the prune; and
generate a user interface comprising the plot of the average age of the plurality of files retained after the prune.

2. The non-transitory computer-readable medium of claim 1 , further comprising program code that, when executed, causes the at least one computing device to:
generate an administrative user interface configured to receive information to be used in the prune, the information comprising at least:
the desired average age; and
a selection of whether to prune the files according to a time of creation or a time of modification of the plurality of files, the age and the desired average age being determined based at least in part on the selection.

3. The non-transitory computer-readable medium of claim 1 , wherein the count of the plurality of files having the timestamp more recent than the age of the first one of the plurality of files is approximated by:

N
⁡

(
t
)

=

∫
0
t

⁢

ρ
0

⁢

ⅇ

-
λ

⁢

⁢
t

=

ρ
0

λ

⁢

(

1
-

ⅇ

-
λ

⁢

⁢
t

)

,

wherein t is time,

1
λ

is the desired average age of the plurality of files, and an initial sample density is represented as ρ 0 .

4. The non-transitory computer-readable medium of claim 1 , wherein:
the first index associated with the potential storage location in the memory device is identified by rounding up the count; and
the second index associated with the potential storage location in the memory device is identified by rounding down the count.

5. A system, comprising:
at least one computing device comprising hardware processing circuitry and memory accessible to the at least one computing device, the memory comprising a plurality of data items; and
program instructions executable in the at least one computing device that, when executed, cause the at least one computing device to:
perform a prune of the plurality of data items residing in a memory device using a continuous pruning function such that an average age of the plurality of data items retained after the prune fits an exponential decay curve and the average age of the plurality of data items matches a desired average age, by:
estimating, for a first one of the plurality of data items, a count of the plurality of data items younger than the first one of the plurality of data items based at least in part on a comparison of a plurality of timestamps associated with individual ones of the plurality of data items;
determining at least one index associated with a potential storage location in the memory for the first one of the plurality of data items based at least in part on the count; and
applying a binning function that causes a first portion of the plurality of data items to be deleted and a second portion of the plurality of data items to be retained, wherein the binning function comprises determining whether to replace a second one of the plurality of data items residing in the storage location in the memory associated with the at least one index with the first one of the plurality of data items by comparing the age of the first one of the plurality of data items to an age of the second one of the plurality of data items residing in the storage location in the memory associated with the at least one index.

6. The system of claim 5 , wherein the desired average age is provided by a user.

7. The system of claim 5 , wherein performing the prune further comprises transmitting a notification to a second computing device comprising information associated with the determination whether to store the first one of the plurality of data items at the index.

8. The system of claim 5 , wherein the plurality of data items further comprise a plurality of files.

9. The system of claim 5 , wherein the plurality of timestamps are associated with a time of creation of the plurality of data items.

10. The system of claim 5 , wherein the plurality of timestamps are associated with a time of modification of the plurality of data items.

11. The system of claim 8 , wherein performing the prune further comprises forecasting, before the prune is co

Assignees

• Mikula John C
• Amazon Tech Inc

Inventors

• Mikula John C

Classifications

• G06F3/0683

  Plurality of storage devices · CPC title

• G06F16/1737 Primary

  for reducing power consumption or coping with limited storage space, e.g. in mobile devices (saving storage space on storage devices G06F3/0608; power saving in storage systems G06F3/0625) · CPC title

• G06F11/14

  Error detection or correction of the data by redundancy in operations (error detection or correction of the data by redundancy in hardware G06F11/16) · CPC title

• G06F3/0652

  Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket · CPC title

• G06F3/0608

  Saving storage space on storage systems · CPC title