Centralized Coded Caching of Correlated Contents
Qianqian Yang and Deniz Gündüz

arXiv:1711.03798v1 [] 10 Nov 2017

Information Processing and Communications Lab
Department of Electrical and Electronic Engineering
Imperial College London

Abstract—Coded caching and delivery is studied taking into
account the correlations among the contents in the library.
Correlations are modeled as common parts shared by multiple
contents; that is, each file in the database is composed of a
group of subfiles, where each subfile is shared by a different
subset of files. The number of files that include a certain subfile
is defined as the level of commonness of this subfile. First,
a correlation-aware uncoded caching scheme is proposed, and
it is shown that the optimal placement for this scheme gives
priority to the subfiles with the highest levels of commonness.
Then a correlation-aware coded caching scheme is presented, and
the cache capacity allocated to subfiles with different levels of
commonness is optimized in order to minimize the delivery rate.
The proposed correlation-aware coded caching scheme is shown
to remarkably outperform state-of-the-art correlation-ignorant
solutions, indicating the benefits of exploiting content correlations
in coded caching and delivery in networks.

I. I NTRODUCTION
In proactive caching, popular contents are stored in user
devices during off-peak traffic periods even before they are
requested by the users [1]–[3]. Proactive caching is considered as a promising solution for the recent explosive growth
of wireless data traffic, and can alleviate both the network
congestion and the latency during peak traffic periods (see
[1]–[4], and references therein).
Proactive caching typically takes place in two phases: the
first phase takes place during off-peak traffic periods, when
users’ caches are filled as a function of the whole library of
files, referred to as the placement phase; while the second,
delivery phase, takes place during the peak traffic period when
the users’ demands are revealed and satisfied simultaneously.
In contrast to traditional uncoded caching schemes, which
simply employ orthogonal unicast transmissions during the
delivery phase, recently proposed coded caching [4] creates
coded multicasting opportunities, significantly reducing the
amount of data that needs to be delivered to the users to satisfy
their demands, even when these demands are distinct. Coded
caching benefits from the aggregate cache capacity across the
network, rather than local cache capacities as in conventional
uncoded caching [4]. This significant improvement has motivated intense research interest on coded caching in recent years
[5]–[12]. Some works follow the simplified model proposed
in [4], and aim to improve the fundamental limits of caching
[6], [7], [13]; others consider more realistic settings, such
as decentralized caching [5], nonuniform popularities across
files [9], [10], audience retention rate aware caching [14], or
heterogeneous quality of service requirements [12].

An important feature of video contents, which is the main
source of the recent explosive traffic growth, is that, there
may be significant overlaps among different files, e.g., the
recordings of the same event from different angles and different cameras, or even the frames of the same scene in the
same video. In [15], Hassanzadeh et al. propose a correlationaware caching scheme, which groups the contents in the
library into two sets according to their correlations as well
as popularity, where each file in second set is compressed
with respect to a file in the first set. This scheme is shown
to outperform correlation-ignorant caching schemes. A more
information theoretic formulation for caching of correlated
sources is considered in [16], focusing on a special scenario
with two receivers and one cache. A similar informationtheoretic analysis is carried out in [17] for two files and two
receivers, each with its own cache.
In this paper, we consider a server with a library of N
correlated files, serving K users equipped with local caches.
Different from [15], which only exploits a fixed level of
common information among the files, we consider a more general model in order to fully exploit the potential correlations
among different subsets of files. We model each file in the
server to be composed of a group of subfiles, such that each
subfile is shared by a different subset of files. The number of
files to which each subfile belongs is defined as its level of
commonness. Equivalently, in our model, any subset of files
S share a common part that is independent of the rest of the
library, and shared exclusively by the files in S.
We first propose a correlation-aware uncoded caching
scheme, and show that the optimal placement for this scheme
is achieved by giving priority to the subfiles with the highest
levels of commonness in the placement phase. We then propose a correlation-aware coded caching scheme, and derive a
closed-form expression of the achievable delivery rate, based
on which the cache capacity is optimally allocated to the
subfiles according to their level of commonness. Then, we
compare the performance of the proposed correlation-aware
schemes with those that ignore the correlation, and the cutset bound; and show that, exploiting file correlations in coded
caching can significantly reduce the delivery rate.
Notations: The set of integers {i, ..., j}, where i ≤ j, is
denoted by [i : j], particularly, {1, ..., j} is denoted by [j]. For
sets A and B, we define A\B , {x
/ B}, and
 : x ∈ A, x ∈
|A| denotes the cardinality of A. ji represents the binomial
coefficient if j ≥ i; otherwise, ji = 0. For event E, 1{E} =
1 if E is true; and 1{E} = 0, otherwise.

II. S YSTEM M ODEL
We consider a server with a database of N correlated files,
N −1
W1 , ..., WN , where each
independent
S file consists of 2
subfiles, e.g., Wi =
W S , ∀i ∈ [N ]. Here, W S denotes
S⊂[N ]
i∈S

the subfile shared exclusively by the subset of files {Wi : i ∈
S}. For simplicity, we assume that for S ⊂ [N ], |W S | = Fl ,
if |S| = l, i.e., the common subfiles shared exclusively by l
files are of the same size of Fl bits. Let F , (F1 , . . . , FN ).
As a result, each file in the library is also of the same size of
F bits, given by

N 
X
N −1
F =
Fl .
(1)
l−1
l=1

For S ⊂ [N ], |S| = l, we say that the subfiles W S have a
commonness level of l. For example, W {1,2,3} and W {3,4,5}
both have level 3 commonness. For brevity, we refer to all the
subfiles with level l commonness as l-subfiles, l = 1, ..., N .
We consider K users connected to the server through a shared,
error-free link, each equipped with a cache of size M F bits.
We consider centralized caching; that is, the server has the
knowledge of the active users during the placement phase,
though not the knowledge of their demands. Centralized
caching allows the server to fill the user caches in a coordinated manner. After the placement phase, each user requests
a single file from the library, where dk ∈ [N ] denotes user k’s
request, k ∈ [K]. All the requests are satisfied simultaneously
over the error-free shared link.
An (F, M, R) caching code for this system consists of:
• K caching functions fk , k ∈ [K],
fk : [2F ] × · · · × [2F ] → [2M F ],
{z
}
|

(2)

such that the contents of user k’s cache at the end of
the placement phase, denoted by Zk , is given by Zk =
fk ({Wi }N
i=1 );
a delivery function g,
g : [2F ] × · · · × [2F ] ×D → [2RF ],
|
{z
}

(3)

N files

•

where D , (d1 , ..., dK ), such that a single message of
RF bits, XD = g((W1 , ..., WN ), D), is sent by the server
over the shared link according to users’ demands;
K decoding functions hk , k ∈ [K],
hk : D × [2

MF

] × [2

RF

F

] → [2 ],

(4)

where Ŵdk = hk (D, Zk , XD ), is the reconstruction of
Wdk at user k.
Definition 1. A user cache capacity-delivery rate pair (M, R)
is achievable for a system described above, if there exists
a sequence of (F, M, R) codes such that for any demand
realization D ⊂ [N ]K ,


 [ n
o
lim
Pr
Ŵdk 6= Wdk
= 0.
(5)
F1 ,...,FN →∞


k∈[K]

III. C ORRELATION - AWARE U NCODED C ACHING AND
D ELIVERY (CAUC) S CHEME
We first present an uncoded caching and delivery scheme
exploiting the correlation among files, referred to as CAUC.
1) Placement phase: Each user caches the same pl Fl bits
from each l-subfile, where 0 ≤ pl ≤ 1, l ∈ [N ], such that
N  
X
N
MF =
pl Fl ,
(6)
l
l=1

which meets the limitation of the cache capacities. We refer
to P , (p1 , ..., pN ) as the cache allocation vector, which will
be specified in the sequel.
2) Delivery phase: The server delivers the remaining bits
of each requested subfile that have not been cached by the
K
P
1{dk ∈ S} ≥ 1.
users, i.e., W S for which
k=1

In the worst case, when the demand combination is the most
distinct, i.e., users request distinct files for the case N ≥ K, or
each file is requested by at least one user for the case N < K,
the delivery rate is given by
  

N
X
N
min{N − K, 0}
(1 − pl )Fl
RCAU C (P) =
−
.
l
l
l=1
(7)
The optimal P∗ can be derived by solving the following
optimization problem
min

N files

•

For a system with N files and K users, our goal is to
characterize the minimum achievable rate R as a function
of the user cache capacity M , i.e., R∗ (M ) , inf{R :
(M, R) is achievable}.

RCAU C (P)
N  
X
N
such that
pl Fl ≤ M F,
l

(8)

l=1

which, straightforwardly, leads to: p∗l = 1, if C(l) ≤ M F ;
, if C(l + 1) < M F < C(l); and p∗l =
p∗l = M F −C(l+1)
(Nl )Fl
N

P
N
0, otherwise; where we have defined C(l) ,
i Fi , for
i=l

l ∈ [N ]. We remark that the optimal cache allocation gives
priority to the subfiles with the highest level of commonness.
IV. C ORRELATION - AWARE C ODED C ACHING AND
D ELIVERY (CACC) S CHEME
In this section, we present a correlation-aware coded
caching and delivery scheme, referred to as CACC. Similarly
to the CAUC scheme, we allocate different cache capacities to
subfiles of different levels of commonness, again specified by
the cache allocation vector, P = (p1 , ..., pN ), which satisfies
the constraint in (6), such that each user caches pl Fl bits from
each l-subfile, l ∈ [N ]. In the following, we first present how
coded caching and delivery of the subfiles with the same level
of commonness is carried out, and then specify the allocation
of cache capacity.

A. Coded Caching and Delivery of l-subfiles
Here, for a given cache allocation vector P, we present the
coded caching and delivery of l-subfiles, l ∈ [N ]. We define
tl , Kpl , 0 ≤ tl ≤ K. If tl = 0, users do not cache the
l-subfiles at all, while if tl = K, each user stores all the lsubfiles in its cache. In the following, we focus on the cases
where tl ∈ [K − 1].
1) Placement Phase: We employ the prefetching scheme
proposed by [4] for the subfiles rather than the files themselves: each l-subfile is partitioned into K
disjoint parts,
tl

each with approximately the same size of Fl / K
tl bits. We

A
label these K
tl disjoint parts of each l-subfile W S by W S ,
where |A| = tl , A ⊂ [K]; that is, we have W S =
S
A
A
A:|A|=tl , A⊂[K] W S . Each of these parts, W S , is placed
into the cache of
 user k if k ∈ A. Thus, each user caches
a total of K−1
tl −1 disjoint parts of each l-subfile with a total
size of tl Fl /K bits, which sums up to pl Fl bits.
2) Delivery Phase: We first focus on the case when
N ≤ K. There are a total of Nl l-subfiles. We denote the
set of these l-subfiles by W l = W
 S : S ⊂ [N ], |S| = l .
N −1
Each user requires a total of l−1 l-subfiles, i.e., user k

needs to recover subfiles in W S : S ⊂ [N ], |S| = l,
 dk ∈ S ,
−1
∀k ∈ [K]. For each user, we can regard these Nl−1
l-subfiles

−1
as Nl−1
distinct demands. Our delivery scheme for the l
−1
subfiles operates in Nl−1
steps, and satisfies one demand of
each user at each step.
We define Cj , (c1j , ..., cN j ), where cij ∈ {S : S ⊂
−1
[N ], |S| = l, i ∈ S}, ∀i ∈ [N ], j ∈ [ Nl−1
], which specifies
which subfile should be delivered in the jth step of the delivery
phase. Cj is generated by Algorithm 1 by setting R = [N ] and
R = ∅. Note that these vectors are generated independently
of the number of users or their demands.
Example 1. Consider N = 5 and l = 2. From Algorithm 1
we obtain:

Algorithm 1 Generate Cj , j ∈ [
1:
2:
3:
4:
5:
6:
7:
8:

9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:

|R|−1 
]
l−R−1

procedure A SSIGNMENT
Wt ← W l , j ← 1, Wlast ← ∅, clast ← ∅
while Wt 6= ∅ do
ct ← R
while ct 6= ∅ do
if |ct | ≥ l − |R| then
if clast = ∅ then
Randomly select one l-subfile W S from
Wt such that S \ R ⊂ ct , remove W S from Wt , and
ct ← ct \ S
for i ∈ S \ R do
cij ← Wlast
end for
else
for i ∈ clast \ R do
cij ← S
end for
ct ← ct \ clast , Wlast ← −1, and
clast ← ∅
end if
else
Randomly select one l-subfile W S from
Wt such that ct ⊂ S
for i ∈ ct do
cij ← S
end for
for i ∈ R do
cij ← ∅
end for
Wlast ← S, clast ← S \ ct , ct ← ∅, and
j ←j+1
end if
end while
end while
end procedure

C1 = ({1, 2}, {1, 2}, {3, 4}, {3, 4}, {1, 5});
C2 = ({1, 5}, {2, 3}, {2, 3}, {4, 5}, {4, 5});
C3 = ({1, 3}, {2, 5}, {1, 3}, {2, 4}, {2, 5});
C4 = ({1, 4}, {2, 4}, {3, 5}, {1, 4}, {3, 5}).
This means, for example, that, in the first step, subfiles
W12 , W34 , and W15 will be delivered (if there is a user
requesting them).
We denote by djk , cdk j the demand of user k to be satisfied
in the jth step, i.e., user k recovers W dj after the jth step.
k
−1
(Nl−1
S)
W cij = {W S : S ∈ [N ], |S| =
We emphasize that
j=1

l, i ∈ S}, ∀i ∈ [N ]; that is all the required
 l-subfiles will
−1
be recovered by each user after step Nl−1
for any demand
combination.
Example 2. Consider N = K = 5 and l = 2 as in Example
1. Consider distinct demands, i.e., D = {1, 2, 3, 4, 5}. Thus,

based on C1 , we have d11 = d12 = {1, 2}, d13 = d14 = {3, 4},
and d15 = {1, 5}; that is, at the end of the first step, users 1
and 2 should recover W12 , users 3 and 4 should recover W34 ,
while user 5 should recover W15 .
Example 3. With the same setting as in Example 2, consider
now a non-distinct demand combination D = {1, 1, 1, 3, 4}.
Based on C1 , we have d11 = d12 = d13 = {1, 2}, and d14 =
d15 = {3, 4}; that is, at the end of the first step users 1, 2
and 3 should recover W12 , while users 4 and 5 should recover
W34 .
Based on the delivery scheme proposed in [13], we present
our coded transmission
scheme in Algorithm 2 according to

−1
Cj , j ∈ [ Nl−1
], where R = ∅, R = [N ]. In Algorithm 2, we

−1
define Aj as the number of distinct djk for each j ∈ [ Nl−1
].
We note that, among the CODED DELIVERY and RANDOM

Algorithm 2 Coded transmission based on Cj
procedure C ODED D ELIVERY
for k = 1, ..., K do
djk ← cdk j
4:
end for
j
5:
Uj ← Any subset of Aj users
Pwith distinct dk
6:
for V ⊂ [K] : |V| = tl + 1,
1{k ∈ V} ≥ 1 do
1:
2:
3:

k∈Uj

L
V\{k}
.
Send k∈V W dj
k
8:
end for
9: end procedure
7:

procedure R ANDOM D ELIVERY
for S ⊂ R : |S| = l − |R| do
Server sends enough random linear combinations
of the bits of l-subfile W S∪R to enable the users demanding it to decode it.
13:
end for
14: end procedure

10:
11:
12:

DELIVERY procedures of Algorithm. 2, the one that requires
a smaller delivery rate is performed.
Example 2 - continued. In Example 2, assume that tl = 1,
i.e., each l-subfile is divided into K disjoint parts of equal
size, and each disjoint part is cached exactly by one user.
Based on D, we have A1 = 3. Assume that U1 = {1, 3, 5}.
{1} L
{2}
{1} L
{3}
Then, the server sends W {1,2} W {1,2} , W {3,4} W {1,2} ,
{1} L
{4}
{1} L
{5}
{2} L
{3}
W {3,4} W {1,2} , W {1,5} W {1,2} , W {3,4} W {1,2} ,
{3} L
{4}
{5} L
{3}
{2} L
{5}
W {3,4} W {3,4} , W {3,4} W {1,5} , W {1,5} W {1,2} ,
{4} L
{5}
W {1,5} W {3,4} . By receiving these coded bits, users 1
and 2 can recover W {1,2} together with the contents of their
own caches. Similarly, users 3 and 4 can recover W {3,4} ,
while user 5 recovers W {1,5} . In the same manner, by coded
transmission based on C2 , user 1 can recover W {1,5} , users
2 and 3 recover W {2,3} , and users 4 and 5 recover W {4,5} in
the second step. After four delivery steps based on C1 , . . . ,
C4 each user decodes all the 2-subfiles of their requests. The
total number of bits delivered in these four steps is 36F2 /5.
Example 3 - continued. Assume again that t = 1.
Based on D, we have A1 = 2, and let U1 = {1, 4}. Then,
{1} L
{2}
{1} L
{3}
the server sends W {1,2} W {1,2} , W {1,2} W {1,2} ,
{1} L
{4}
{1} L
{5}
{2} L
{4}
W {3,4} W {1,2} , W {3,4} W {1,2} , W {3,4} W {1,2} ,
{3} L
{4}
{5} L
{4}
W {3,4} W {1,2} , W {3,4} W {3,4} , such that users 1, 2
and 3 can recover W {1,2} , while users 4 and 5 can recover
{1} L
{2}
W {3,4} . Based on C2 , the server sends W {1,5} W {1,5} ,
{1} L
{3}
{1} L
{4}
{1} L
{5}
W {1,5} W {1,5} , W {2,3} W {1,5} , W {4,5} W {1,5} ,
L
L
L
{2}
{4}
{3}
{4}
{5}
{4}
W {2,3} W {1,5} , W {2,5} W {1,5} , W {2,3} W {4,5} ,
L
L
{2}
{5}
{3}
{5}
W {4,5} W {1,5} , W {4,5} W {1,5} , such that users 1, 2
and 3 can recover W {1,5} , while user 4 and user 5 can
recover W {2,3} and W {4,5} , respectively. Based on C3 ,

{1} L
{2}
{1} L
{3}
the server sends W {1,3} W {1,3} , W {1,3} W {1,3} ,
L
L
L
{1}
{4}
{1}
{5}
{2}
{5}
W {1,3} W {1,3} , W {2,4} W {1,3} , W {2,4} W {1,3} ,
L
L
{3}
{5}
{4}
{5}
W {2,4} W {1,3} , W {2,4} W {1,3} , based on which users
1,2,3 and 4 can recover W {1,3} , while user 5 recovers W {2,4} .
{1} L
{2}
Finally, based on C4 , the server sends W {1,4} W {1,4} ,
L
L
L
{1}
{3}
{1}
{5}
{1}
{4}
W {1,4} W {1,4} , W {1,4} W {1,4} , W {3,5} W {1,4} ,
{2} L
{4}
{3} L
{4}
{5} L
{4}
W {3,5} W {1,4} , W {3,5} W {1,4} , W {3,5} W {1,4} ,
such that users 1, 2, 3 and 4 are able to recover W {1,4} ,
while user 4 recovers W {3,5} . Thus, all the users are able
to decode the 2-subfiles they requested. The total number of
bits delivered in this case is 30F2 /5.
Next, we consider the case N > K. We first select a subset
of K files R, R ⊂ [N ], such that |R| = K, and dk ∈ R
for k = 1, ..., K. For any subset R ∈ [N ] \ R, |R| = s,
s ∈ [max{l − K, 0} : min{l − 1, N − K}}], Algorithm 1
is applied to a subset of l-subfiles W l = {W S∪R : S ⊂
|R|−1 
R, |S| = l − |R|} to derive Cj , j ∈ [ l−R−1 ], based on
which Algorithm 2 is applied to enable each user to decode
its demanded l-subfiles in W l . Therefore, each user can decode
all the l-subfiles it is demanding.

B. Achievable rate
The following theorem presents the delivery rate achieved
by the proposed coded caching and delivery scheme for any
demand combination, for a given cache allocation vector P.
Theorem 1. For the caching system described in Section II,
given a cache allocation vector P, the following delivery rate
is achievable
N
X

RCACC (P) =

Rl (tl ),

(9)

l=1

where tl = pl K, and for tl ∈ [0 : K],
Rl (tl ) = min{αl (tl ), ml (tl )},

(10)

and
max{min{l−1,N −K},0} 


min{N, K} − 1
·
l−s−1
s=max{l−K,0}
"
 
#
K
max{K − d min{N,K}
e − 1, 0}
Fl
l−s
−
,
tl + 1
tl + 1
F K
tl
(11)
  

N
min{N − K, 0}
ml (tl ) ,
−
(Fl − tl Fl /K)/F.
l
l
(12)
For tl ∈
/ [0 : K], Rl (tl ) is given by the lower convex envelop
of the above achievable points.
αl (tl ) ,

X

N −K
s



Proof. We show that Rl (tl ) given above is achievable tl ∈
[0 : K]. The lower convex envelop of these integer points can
then be achieved by memory sharing. For the case N ≤ K,
−1
recall that the requested l-subfiles are delivered in Nl−1
steps

N −1
based on Cj , j = [ l−1 ], derived by Algorithm 1. In each
step, the server sends at most dN/le + 1 l-subfiles. Therefore,
for any demand combination, the number of distinct djk based


−1
on Cj , i.e., Aj ≤ dN/le + 1, n = 1, ..., Nl−1
. Similar to the
delivery scheme proposed in [13], by the CODED DELIVERY
procedure of Algorithm 2, the server broadcasts binary sums
that help at least one user in Uj based on Cj . The total number
of such subsets of t1 + 1 users that contain at least one user
max{K−dN/le−1,0}
in Uj is given by tlK
. Hence, given
+1 −
tl +1
tl ∈ {1, ..., K − 1}, the total number of bits sent by CODED
DELIVERY procedure of Algorithm 2 for the delivery of the
l-subfiles is bounded by (normalized by F ):
Rl (tl ) ≤

N − 1  K  max{K − dN/le − 1, 0} F
l
−

tl + 1
tl + 1
l−1
F K
tl
(13)

The right hand side (RHS) of 13 is equal to (11) for N ≤ K.
Since each user caches tl Fl /K bits of each l-subfile, according
to [5, Appendix A], the number of bits sent by the RANDOM
DELIVERY procedure is bounded by
Rl (tl ) ≤

N 
(Fl − tl Fl /K)/F.
l

(14)

The RHS equals to (12) for N ≤ K. Hence, for tl ∈
{1, ..., K − 1}, we have proven Rl (tl ) given in (10) is
achievable for N ≤ K.
We then focus on the case where N > K. For any
max{l− K, 0} ≤ s ≤ min{l − 1, N − K}, there are a total of
N −K
subsets R such that R ∈ [N ] \ R, |R| = s. Following
s
the similar analysis for the case where N ≤ K, given R containing all the demanded files such that |R| = K, and any R
such that R ∈ [N ] \ R, |R| = s, requested l-subfilesin W l =
K−1
{W S∪R : S ⊂ R, |S| = l − |R|} are sent in l−s−1
step. At
N
each step, there are at most d l−s e + 1 l-subfiles to be sent.
Therefore, with similar arguments, the total number of bits sent
by CODED DELIVERY
procedure of Algorithm 2 in each
 step
 K 
N
max{K−d l−s
e−1,0}
K−1
Fl
is bounded by l−s−1
,
tl +1 −
tl +1
F (K
tl )
while the number of bits send by the RANDOM DELIVERY
K
procedure is bounded by l−s
(Fl − tl Fl /K)/F . By summing

N −K
over all
subsets R for each s ∈ [max{l − K, 0} :
s
min{l − 1, N − K}], we have
min{l−1,N −K} 

N − K  K − 1 
·
s
l−s−1
s=max{l−K,0}
!
 K  max{K − d N e − 1, 0}
Fl
l−s
−
,
tl + 1
tl + 1
F K

Rl (tl ) ≤

C. Allocation of Cache Capacity
We can further optimize the cache content distribution P
by solving:
min RCACC (P)
N  
X
N
such that
pl Fl ≤ M F,
l

(17a)
(17b)

l=1

where the objective is to minimize the achievable delivery rate
under the cache capacity constraint. The problem in (17) can
be solved numerically.

X

(15)

tl

min{l−1,N −K} 

X

s=max{l−K,0}

N − K  K 
(Fl − tl Fl /K)/F,
s
l−s

V. L OWER B OUND
In this section, we present a lower bound derived using cutset arguments.

and,
Rl (tl ) ≤

Fig. 1. Delivery rate (R) vs. ratio of 2-subfiles (r2 ),r3 = · · · = r10 = 0.

(16)

by which, we have proven the correctness of (10) for the case
N > K.
Remark 1. At each step of sending l-subfiles in W l =
{W S∪R : S ⊂ R, |S| = l − |R|}, there are sometimes
N
N
d l−s
e + 1 and sometimes d l−s
e distinct demands, while when
N
distinct demands
N is a multiple of l−s, there are always l−s
(R = [N ], R = ∅, s = 0, for the case N ≤ K). To obtain
a closed-form expression for the achievable delivery rate, we
N
simply assume d l−s
e + 1 distinct demands at each step. Note
that, the more the number of distinct demands at each step,
the larger the delivery rate. Therefore RCACC (P) in (9) is an
upper bound on the actual achievable delivery rate of CACC.

Theorem 2. (Cut-set Bound) For the caching problem described in Section II, the optimal achievable delivery rate is
lower bounded by
N −pbN/pc pbN/pc 
X
X N − pbN/pc
R∗ (M ) ≥
max
·
s
p∈[1:min{N,K}]
s=0
l=1


pM
pbN/pc Fl+s
−
.
(18a)
l
bN/pc bN/pc
Proof. The proof will be provided in a longer version of the
paper.
VI. N UMERICAL RESULTS
In this section, we numerically compare the delivery rates
of the proposed correlation-aware caching schemes CAUC and
CACC with the lower bound and the state-of-the-art coded
caching scheme from [13], which does not take the content

VII. C ONCLUSIONS
We have studied coded caching taking into account the
available correlations among the files in the library. To capture
arbitrary correlations, we assume that each file consists of a
number of subfiles, each of which is shared by a different
subset of files in the library, and the number of files that share
a certain subfile is defined as its level of commonness. We
proposed both a correlation-aware uncoded caching scheme,
the optimal placement of which is proven to be caching
the subfiles with the highest levels of commonness, and a
correlation-aware coded caching scheme (CACC), the placement of which is optimized in terms of the achievable delivery
rate. The proposed CACC scheme, or even the uncoded
caching scheme when the correlation among files is strong
enough, is shown to significantly outperform the best known
achievable delivery rate by correlation-unaware solution in the
literature.
R EFERENCES

Fig. 2. Delivery rate (R) vs. ratio of 10-subfiles (r10 ), r2 = · · · = r10 = 0.

correlations into account. We refer to the later scheme as the
correlation-ignorant coded caching scheme (CICC).
We consider N = 10 files and k = 10 users. Each user
is equipped with a cache of size F bits, i.e., M = 1. We
denote by rl the ratio of l-subfilesPamong each file, i.e., rl ,
K
N −1
l=1 rl = 1. In Fig. IV-C,
l−1 Fl /F . Note that, we have
we assume that the files have only pairwise correlations, that
is, r3 = · · · = r10 = 0, and we plot the delivery rate as a
function of r2 . Meanwhile, in Fig. VI, we assume that each
file consists of a private part, i.e., 1-subfile, and a common
subfile that is shared by all the files in the library, i.e., 10subfile, i.e., r2 = · · · = r9 = 0. We plot the delivery rate as a
function of r10 .
We observe in both figures that the delivery rate achieved
by the correlation-ignorant scheme, CICC, remains the same
no matter how high the ratio of common subfiles, while the
delivery rates of the correlation-aware schemes, CAUC and
CACC, decrease as the ratio of the common subfiles increases.
Obviously, CACC achieves a lower delivery rate than both
CAUC and CICC, since it benefits both from incorporating
the correlations among the files as well as coded multicasting.
When the ratio of the common subfiles is sufficiently large,
even without coded multicasting CAUC achieves a lower
delivery rate than CICC. It can also be observed that the
delivery rates of correlation-aware schemes decrease faster
with the percentage of common subfiles in Fig. VI than in Fig.
IV-C. That is because the gain from exploiting correlation is
more pronounced as the common parts are shared among more
files. While there is a gap between the cut-set lower bound and
the achievable delivery rate, we note that the gap is smaller in
Fig VI, where the level of commonness is higher.

[1] M. Gregori, J. Gomez-Vilardebo, J. Matamoros, and D. Gündüz, “Wireless content caching for small cell and D2D networks,” IEEE J. Sel.
Areas Commun., vol. 34, no. 5, pp. 1222–1234, Mar 2016.
[2] E. Bastug, M. Bennis, and M. Debbah, “Living on the edge: The role
of proactive caching in 5g wireless networks,” IEEE Communications
Magazine, vol. 52, no. 8, pp. 82–89, Aug 2014.
[3] S. O. Somuyiwa, A. György, and D. Gündüz, “Improved policy representation and policy search for proactive content caching in wireless
networks,” in Proc. IEEE Int’l Symp. on Modeling and Opt. in Mobile,
Ad Hoc, and Wireless Netw. (WiOpt), Paris, France, May 2017.
[4] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,”
IEEE Trans. Inform. Theory, vol. 60, no. 5, pp. 2856–2867, May 2014.
[5] ——, “Decentralized caching attains order optimal memory-rate tradeoff,” IEEE/ACM Trans. Netw, vol. 23, no. 4, pp. 1029–1040, Apr. 2014.
[6] M. Mohammadi Amiri, Q. Yang, and D. Gündüz, “Coded caching for a
large number of users,” in Proc. IEEE Inform. Theory Workshop (ITW),
Cambridge, UK, Sep. 2016, pp. 171–175.
[7] M. Mohammadi Amiri and D. Gündüz, “Fundamental limits of coded
caching: Improved delivery rate-cache capacity trade-off,” IEEE Trans.
Commun., vol. 65, no. 2, pp. 806–815, Feb. 2017.
[8] J. Gomez-Vilardebo, “Fundamental limits of caching: Improved bounds
with coded prefetching,” arXiv:1612.09071v2 [], Jan. 2017.
[9] M. Ji, A. M. Tulino, J. Llorca, and G. Caire, “Order-optimal rate
of caching and coded multicasting with random demands,” arXiv:
1502.03124v1 [], Feb. 2015.
[10] U. Niesen and M. A. Maddah-Ali, “Coded caching with nonuniform
demands,” IEEE Trans. Inform. Theory, vol. 63, no. 2, pp. 1146–1158,
Feb. 2017.
[11] R. Pedarsani, M. A. Maddah-Ali, and U. Niesen, “Online coded
caching,” in Proc. IEEE Int’l Conf. Commun. (ICC), Sydney, Australia,
Jun. 2014, pp. 1878–1883.
[12] Q. Yang and D. Gündüz, “Coded caching and content delivery with
heterogeneous distortion requirements,” arXiv:1608.05660v1 [],
Aug. 2016.
[13] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “The exact ratememory tradeoff for caching with uncoded prefetching,” in Proc. IEEE
Int’l Symp. on Inform. Theory (ISIT), Aachen, Germany, Jun 2017, pp.
1613–1617.
[14] Q. Yang, M. Mohammadi Amiri, and D. Gündüz, “Audience retention
rate aware coded video caching,” in Proc. IEEE Int’l Conf. on Commun.
Workshop (ICC Workshop), Paris, France, Jun. 2017, pp. 1189–1194.
[15] P. Hassanzadeh, A. Tulino, J. Llorca, and E. Erkip, “Correlation-aware
distributed caching and coded delivery,” in Proc. IEEE Inform. Theory
Workshop (ITW), Cambridge, UK, Sep. 2016, pp. 166–170.
[16] R. Timo, S. S. Bidokhti, M. Wigger, and B. C. Geiger, “A rate-distortion
approach to caching,” arXiv:1610.07304v1 [], Oct. 2016.
[17] P. Hassanzadeh, A. Tulino, J. Llorca, and E. Erkip, “Rate-memory tradeoff for the two-user broadcast caching network with correlated sources,”
arXiv:1705.04616v1 [], May 2017.

