METHOD FOR STORING OBJECTS IN A STORAGE AND CORRESPONDING SYSTEM

1 : A method for storing objects in a storage, wherein the storage has a predetermined capacity, the method comprising:

providing an expected popularity and an uncertainty of the expected popularity for each of the objects,

selecting a set of the objects for storing in the storage, wherein the set of is selected on the basis of the expected popularity, the uncertainty and the capacity of the storage.

2 : The method according to claim 1 , wherein the storage is a distributed caching infrastructure or a logistic storage.

3 : The method according to claim 1 , wherein the uncertainty includes one or more of the variance, the standard deviation, and/or the relative standard deviation of the expected popularity.

4 : The method according to claim 1 , wherein the selecting the set of the objects is configured in such a way that a hit ratio representing a fraction of requested objects that are placed in the storage is maximized.

5 : The method according to claim 1 , wherein a hit ratio hr(T) over a time interval T is defined according to

hr



(

T

)

=

∑

i

∈

O

storage

⋂

Q



(

r

)



p

i

∑

i

∈

Q



(

T

)



p

i

wherein Q(T) is the number of requested objects during the time interval T, wherein O storage is the set of objects stored in the storage and wherein p i (T) is the popularity of an object o i for the time interval T.

6 : The method according to claim 1 , wherein the step of selecting the set of the objects includes computing a solution of a bi-dimensional knapsack problem such that the hit ratio of requested objects stored in the storage is maximized, wherein said bi-dimensional knapsack problem considers a capacity constraint and a popularity uncertainty constraint.

7 : The method according to according to claim 1 , wherein the step of selecting the set of the objects includes computing a solution of a bi-dimensional knapsack problem according to

max

x



∑

i

=

1

N



μ

i

·

x

i

which is subject to the constraints that

∑

i

=

1

N



s

i

·

x

i

≤

C





and

∑

i

=

1

N



σ

i

μ

i

·

x

i

≤

W





and

x

i

∈

{

0

,

1

}

,

∀

1

≤

i

≤

N

wherein μ i is the expected popularity for an object o i , wherein x i is 1 for a selected object o i , wherein x i is 0 for a unselected object o i , wherein s i is the size of an object o i , wherein C is the capacity of the storage, wherein σ i is the standard deviation of an expected popularity μ i , and wherein W is a risk envelope for a popularity uncertainty constraint.

8 : The method according to claim 1 , wherein a number of N objects o 1 , . . . o N have expected popularity μ 1 , . . . , μ N , wherein the step of selecting the set of the objects is configured such that a probability of being able to serve a predetermined number of requests is maximized by computing a solution of an optimization problem according to

min

x

∈

{

0

,

1

}

N



τ

-

∑

i

=

1

N



µ

i



x

i

∑

i

=

1

N



σ

i



x

i

which is subject to the constraints that

∑

i

=

1

N



s

i

·

x

i

≤

C





and

x

i

∈

{

0

,

1

}

,

∀

1

≤

i

≤

N

wherein parameter τ represents the predetermined number of requests, wherein s i is the size of an object o i , wherein x i is 1 for a selected object o i , wherein x i is 0 for a unselected object o i , wherein μ i is the expected popularity for an object o i , wherein σ i is the standard deviation of an expected popularity μ i , and wherein C is the capacity of the storage.

9 : The method according to claim 1 , wherein a dynamic programming algorithm is employed for selecting the set of the objects.

10 : The method according to claim 1 , wherein a greedy algorithm is employed for selecting the set of the objects, wherein an object that appears to yield the largest profit is iteratively selected while a capacity constraint and/or a popularity uncertainty constraint is/are satisfied.

11 : The method according to claim 1 , wherein an object's profit is computed on the basis of an efficiency metric.

12 : The method according to claim 1 , wherein the efficiency metric is specified as

e

i

=

μ

i

σ

i

,

∀

1

≤

i

≤

N

wherein μ i is the expected popularity for an object o i , and wherein σ i is the standard deviation of an expected popularity μ i .

13 : The method according to claim 1 , wherein the efficiency metric is specified as

e

i

=

μ

i

s

i

C

+

w

i

W

,

∀

1

≤

i

≤

N

wherein μ i is the expected popularity for an object o i , wherein s i is the size of an object o i , wherein C is the capacity of the storage, wherein w i is the relative standard deviation σ i /μ i , wherein σ i is the standard deviation of an expected popularity μ i , and wherein W is a risk envelope.

14 : The method according to claim 1 , wherein the selected set of objects is employed for loading an empty storage, and/or

wherein the selected set of objects is employed for updating the storage at a predetermined time interval, and/or

wherein the selected set of objects is employed for updating the storage on demand, preferably at stochastic time intervals.

15 : A system for storing objects in a storage, wherein the storage has a predetermined capacity, the system comprising:

a prediction processor configured to predict an expected popularity and an uncertainty of the expected popularity for each of the objects, by use of a forecasting algorithm, and

a selection processor configured to select a set of objects for storing in the storage, wherein the set of objects is selected on the basis of the expected popularity, the uncertainty and the capacity of the storage.