1

Caching Policy for Cache-enabled D2D
Communications by Learning User Preference
Binqiang Chen and Chenyang Yang

arXiv:1707.08409v2 [cs.IT] 3 Jan 2018

Abstract
Prior works in designing caching policy do not distinguish content popularity with user preference.
In this paper, we illustrate the caching gain by exploiting individual user behavior in sending requests.
After showing the connection between the two concepts, we provide a model for synthesizing user
preference from content popularity. We then optimize the caching policy with the knowledge of user
preference and active level to maximize the offloading probability for cache-enabled device-to-device
communications, and develop a low-complexity algorithm to find the solution. In order to learn user
preference, we model the user request behavior resorting to probabilistic latent semantic analysis, and
learn the model parameters by expectation maximization algorithm. By analyzing a Movielens dataset,
we find that the user preferences are less similar, and the active level and topic preference of each user
change slowly over time. Based on this observation, we introduce a prior knowledge based learning
algorithm for user preference, which can shorten the learning time. Simulation results show remarkable
performance gain of the caching policy with user preference over existing policy with content popularity,
both with realistic dataset and synthetic data validated by the real dataset.

Index Terms
User preference, Content popularity, Caching policy, D2D, Machine learning, data analysis.

I. I NTRODUCTION
Caching at the wireless edge has become a trend for content delivery [2–4], which can improve
network throughput and energy efficiency as well as user experience dramatically [5, 6].
Owing to the small storage size of each node at the wireless edge, say base station (BS) or user
device, caching in a proactive manner is critical to achieve the performance gain, where future
user demand statistics is exploited [2, 7]. In wireless networks, the contents can be precached
Binqiang Chen and Chenyang Yang are with the School of Electronics and Information Engineering, Beihang University,
Beijing, China, Emails: {chenbq,cyyang}@buaa.edu.cn. Part of this work has been presented in IEEE VTC Spring 2017 [1].

January 4, 2018

DRAFT

2

at each BS [2, 4] or even directly pushed to user device [3]. By caching at BS, backhaul traffic
can be offloaded and backhaul cost can be reduced. By caching at user, wireless traffic can be
further offloaded from peak time to off-peak time [8]. To boost the cache hit rate by precaching
contents at each user that has very limited cache size, cache-enabled device-to-device (D2D)
communications and coded-multicast strategy are proposed [2, 5, 8].
To heap the proactive caching gain, various caching policies have been optimized with diverse
objectives for different networks. Most existing works assume known content popularity, defined
as the probability distribution that every content in a catalog is requested by all users. For
example, the policies for caching at BSs were optimized to minimize average download delay
in [9] and to maximize coverage probability in [10]. The policies for caching at users were
optimized to maximize the offloading gain of cache-enabled D2D networks in [11, 12]. Coded
caching policy was optimized to maximize the average fractional offloaded traffic and average
ergodic rate of small-cell networks in [13]. In these works, every user is assumed to request files
according to content popularity. However, in practice a user actually sends requests according to
its own preference, which may not be identical to content popularity. Noticing such fact, caching
policies at the user groups with different group popularity were optimized in [14] to minimize
the average delay of cache-enabled D2D communications.
To implement above-mentioned proactive caching policies, content popularity needs to be
predicted [15]. Popularity prediction has been investigated for diverse applications such as
advertisement, where content popularity is defined as the accumulated number of requests every
content in a catalog received or the request arrival rate for every content. Numerous methods
have been proposed [16]. By using these prediction methods, the content popularity defined with
probability in [2–6, 9–14] can be obtained as a ratio of the number of requests for each file to
the number of all requests. In cellular networks, the number of users in a cell is much less than
that in a region covered by a content server, and a mobile user may send requests to more than
one BS. Since popularity depends on the group of users who send requests, the local popularity
in a cell may differ from the global popularity observed at a server. Designing proactive caching
policy at wireless edge with predicted global popularity leads to low cache hit rate [7].
Optimizing caching policy for a BS should be based on the local popularity, which is formed
by the users in a cell. In [17], local popularity was predicted as the number of requests received
for each file at a small BS divided by the observation time, i.e., the request arrival rate. Then,
the popularity is adjusted with a perturbation term, which is learned by applying multi-arm

January 4, 2018

DRAFT

3

bandit algorithm, and finally the predicted popularity with perturbation term is used for caching
policy optimization. The prediction is based on the cumulative growth method [16] and under the
assumption that only the requests for already cached files can be observed, hence the learning
algorithm is slow. In [18], the content popularity was predicted with a real dataset measured from
cellular network. By converting the number of requests received at each BS into rating, the local
popularity was predicted by a widely-used collaborative filtering technique, matrix factorization
[19], with which the files with largest ratings are cached at the BS.
A. Motivation and Contributions
Since caching at wireless edge is motivated by the observation that the majority of requests
are initiated for a minority of popular contents, a large body of priori works assume that all
users send their requests according to content popularity. The following facts, which are widely
recognized in the communities studying recommendation problem and analyzing user behavior
with real data, are largely overlooked in the community of studying caching at wireless edge: (i)
as a demand statistic of multiple users, content popularity can not reflect the personal preference
of each individual user [20], (ii) only a small portion of users are active in creating traffic [21].
In fact, existing works do not differentiate content popularity from user preference. In practice,
user preferences are heterogeneous although they may exhibit similarity to a certain extent. The
caching policy designed under unrealistic assumptions inevitably yields performance loss.
In this paper, we investigate the gain of optimizing caching policy by learning user preference
and active level over content popularity. To this end, we take cache-enabled D2D communications
as an example system and offloading probability as an example objective. Because there are
different definitions in the domains of computer science and wireless communications, we first
define user preference and active level as well as content popularity to be used in this paper,
and provide a probabilistic model to synthesize user preference from content popularity by
introducing similarity among user preferences. We then formulate an optimization problem with
known user preference and active level to maximize offloading probability. Since the problem is
NP-hard, a local optimal algorithm is proposed to reduce the complexity, which achieves at least
1/2 optimality. In order to learn user preference and active level, we model user request behavior
resorting to probabilistic latent semantic analysis (pLSA) originally proposed for natural language
processing [22], whose model parameters can be learned using approximate inference methods
such as expectation maximization (EM) [23]. With the help of pLSA model to decompose the user

January 4, 2018

DRAFT

4

behavior into different components and based on the observation from analyzing a real dataset
that active level and topic preference change slowly over time, we provide a prior knowledge
based algorithm, which can quickly learn user preference.
The major contributions of this paper are summarized as follows:
•

We illustrate the caching gain of exploiting user preference and active level by optimizing
an caching policy for D2D communications, and predict the behavior of each individual user
by estimating model parameters of pLSA. We introduce a prior knowledge based algorithm
to learn user preference, which shows the potential of transfer learning.

•

We characterize the connection between content popularity and user preference, provide a
probabilistic model for synthesizing user preference from content popularity, and validate
the method by the MovieLens 1M dataset [24]. We analyze the relation between file catalog
size and the number of users, the statistics of active level and topic preference of each user,
and the user preference by the real dataset, which are critical for the caching gain.

•

Simulation results with both synthesized data and MovieLens dataset show remarkable
performance gain of the caching policy with user preference over that with local popularity,
no matter the user demands are assumed known or learned from historical requests.

B. Related Works
Considering that the tastes of different users are not identical, caching policies were optimized
to minimize the average delay of cache-enabled D2D communications in [25] and to maximize
the cache hit rate of mobile social networks in [26], by assuming user preferences as Zipf
distributions with different ranks. However, both works assume that all users have the same
active level, do not validate the assumption for user preference, and do not show the gain over
caching with popularity. Until now, there exists no method to synthesize user preference validated
by real dataset, and the gain of caching with user preference is unknown.
There are few works that consider the relation between content popularity and user preference.
In [27], local popularity is computed as a weighted average of preferences for the users associated
with each BS, where the weight is the number of requests sent by each user and the user
preference was assumed as uniform distribution. Then, the most popular files at each BS were
cached. Differing from this early work, we characterize the connection between the collective
and the individual user request behavior in a probabilistic framework, and illustrate the gain of
exploiting user preference over popularity by optimizing a caching policy.

January 4, 2018

DRAFT

5

These priori works assume known user preference [25–27]. To facilitate proactive caching, user
preference needs to be predicted, which is a key task in recommendation problem. Collaborative
filtering is the most commonly used technique to predict user preference[19], which can be mainly
classified into memory based method including user-based and item-based approaches, and model
based method that is based on models with parameters estimated from historical records [28].
Typical model based methods employ matrix factorization, latent Dirichlet allocation [29], and
pLSA [30] as models [19]. For recommendation problem, user preference is defined as the rating
that a user gives for a file, such as 0 ∼ 5 or simply “like” and “dislike”. Most collaborative
filtering methods predict the ratings for unrated contents of each user, which however cannot
be used in optimization for wireless caching. To optimize caching policy in wireless edge,
where various metrics are in statistical sense [2–6, 9–14], user preference needs to be defined in
probabilistic form, but there is no widely-accepted approach to map the rating into probability. In
this paper, we resort to pLSA to model and predict user preference, which is originally developed
for classification in automatic indexing [22] and then is applied to predict ratings in [30].
The rest of the paper is organized as follows. Section II provides the relation between content
popularity and user preference, and a model to synthesize user preference. Section III optimizes
the caching policy with known user preference. Section IV presents the learning algorithms.
Section V analyzes the statistics of user demands from and validate the synthetic model by a
MovieLens dataset. Section VI provides simulation results. Section VII concludes the paper.
II. C ONTENT P OPULARITY AND U SER P REFERENCE
In this section, we first define content popularity, user preference and active level to be used
in the following, show their connection, and then provide a probabilistic model with a free
parameter to synthesize user preference.
A. Definition and Relationship
Consider a content library F = {f1 , f2 , ..., fF } consisting of F files that K users in an area
may request, where ff denotes the f th file.
Content popularity is defined as the probability distribution that each file in the library is
requested by all users, denoted as p = [p1 , p2 , ..., pF ], where pf , P (ff ) is the probability that
P
ff is requested, Ff=1 pf = 1, pf ∈ [0, 1], and 1 ≤ f ≤ F . If the area only consists of a single
cellular cell, then p is called local popularity.

January 4, 2018

DRAFT

6

User preference is defined as the conditional probability distribution that a user requests a file
given that the user sends a request, denoted as qk = [q1|k , q2|k , ..., qF |k ] for the kth user (denoted
as uk )), where qf |k , P (ff |uk ) is the conditional probability that the kth user requests the f th
P
file when the user sends a file request, Ff=1 qf |k = 1, qf |k ∈ [0, 1], 1 ≤ f ≤ F and 1 ≤ k ≤ K.
We use matrix Q = (qf |k )K×F to denote the preferences of all users, where (qf |k )K×F represents
a matrix with K rows and F columns and qf |k as the element in the kth row and f th column.
Active level is defined as the probability that a request is sent by a user, denoted as wk , P (uk )
P
for the kth user, which reflects how active the user is, where K
k=1 wk = 1 and wk ∈ [0, 1].
Then, the vector w = [w1 , w2 , ..., wK ] denotes the active level distribution of the K users.
Content popularity p reflects the collective request behavior of a group of users, while qk and
wk characterize the individual request behavior of the kth user. To show their connection, we
consider a K × F user-content matrix [19], where each of its element nk,f represents the number
PF
P
of requests sent by uk for ff . Denote N = K
f =1 nk,f as the overall number of requests
k=1
PK
sent by all the K users for all the F files, nf = k=1 nk,f as the total number of requests sent
P
by all users for ff (i.e., the sum of all elements in the f th column), and nk = Ff=1 nk,f as the
total number of requests sent by uk for all files (i.e., the sum of all elements in the kth row).
Considering that nf /N , nk /N and nk,f /nk are respectively multinomial distributions with F ,
K, and F parameters, it is not hard to show that they are respectively the maximum likelihood
estimate of pf , wk and qf |k . From their definitions, we have
K
X
k=1

nk /N nk,f /nk =
| {z } | {z }
wk

qf |k

K
X
nk,f
k=1

N

= nf /N ,
| {z }

(1)

pf

and hence each element of p can be expressed as the average of user preferences weighted by
their active levels,
pf =

PK

k=1

wk qf |k ,

1 ≤ f ≤ F.

(2)

In practice, users have different tastes, i.e., qk 6= qm , and hence qf |k 6= pf , despite that users
may have similar preferences, say for popular contents. Besides, not all users send requests with
equal probability. We can use cosine similarity to reflect the similarity of preferences between
two users, which is frequently used in collaborative filtering [19] and defined as
sim(qk , qm ) =

January 4, 2018

PF
qf |m qf |k
qP f =1
.
PF
F
2
2
q
f =1 f |m
f =1 qf |k

(3)

DRAFT

7

To show the similarity among K users, we can define average cosine similarity as
Ek,m [sim(qk , qm )] =

2
K(K−1)

PF
qf |k qf |m
qP f =1 P
.
k,m
F
F
2
2
f =1 qf |k
f =1 qf |m

P

(4)

B. Modeling and Synthesizing User Preference
Content popularity can be modeled as a Zipf distribution according to the analyses for many
real datasets [18, 31, 32]. The probability that the f th file is requested by all users is
P
pf = f −β / Fj=1 j −β ,

1 ≤ f ≤ F,

(5)

where the files in the library are indexed in descending order of popularity, and the content
popularity is more skewed with larger value of β.
User preference model obtained from real datasets is unavailable in the literature so far.
Inspired by the method in [7] to synthesize local popularity of a cell from that of a core network,
we represent users and files in a shared one-dimensional latent space, which bears the same spirit
as latent factor model widely applied in collaborative filtering [29, 33]. To connect with content
popularity, we model user preference from the following generative process:
•

uk is associated with a feature value Xk , which is randomly selected from [0, 1].

•

ff is associated with a feature value Yf , which is again chosen uniformly from [0, 1].

•

The joint probability that the f th file is requested by the kth user is given by
g(Xk ,Yf )
,
k0 =1 g(Xk0 ,Yf )

P (uk , ff ) = wk qf |k = pf PK
and then uk ’s active level is wk =

P

ff ∈F

(6)

P (uk , ff ) and its preference is qf |k = P (uk , ff )/wk ,

where g(Xk , Yf ) ∈ [0, 1] is a kernel function used to control the correlation between the
kth user and the f th file. When g(Xk , Yf ) = 0, the f th file will never be requested by the
kth user. When g(Xk , Yf ) = 1, the file is a preferred file of the user.
Intuitively, the value of Xk can be interpreted as the likelihood that the kth user prefers a
topic, and the value of Yf can be interpreted as the likelihood that the f th file belongs to a
topic. Various kernel function can be applied, e.g., Gaussian, logarithmic and power kernels. To
control the average similarity among the user preferences by introducing a parameter α in kernel
1

function, we choose power kernel with expression g(Xk , Yf ) = (1 − |Xk − Yf |)( α3 −1) ∈ [0, 1]
(0 < α ≤ 1), which exhibits a linear relation between Ek,m [sim(qk , qm )] and α in a wide range.
Remark 1: When α = 1, g(Xk , Yf ) = 1 for ∀k, f . Then, we can see from (6) that all user
preferences are identical and equal to the content popularity, and then from (4) we can obtain

January 4, 2018

DRAFT

8

Ek,m [sim(qk , qm )] = 1. When α → 0, g(Xk , Yf ) → 0 for Xk 6= Yf , and g(Xk , Yf ) = 1 only
for Xk = Yf . Because Xk and Yf are uniformly chosen from [0, 1], i.e., P(Xk = Yf ) → 0, we
have g(Xk , Yf )g(Xk0 , Yf ) → 0, k 6= k 0 . Then, according to (6) and (4), Ek,m [sim(qk , qm )] → 0,
i.e., no user has the same preference. When α is small, g(Xk , Yf ) is low, which means that the
number of interested files of uk is small. Because each user randomly chooses feature values, the
interested file sets among different users are less overlapped, and hence the average similarity
among the users is low.
This probabilistic model is appropriate for generating synthetic data of user preference and
active level, which differs from pLSA that can be used for predicting the individual behavior.
This model will be validated later by a real dataset and the parameter will be fitted.
III. C ACHING P OLICY O PTIMIZATION : AN I LLUSTRATION
In this section, we illustrate how to optimize the caching policy with known request behavior
of each individual user. For comparison, we also provide the corresponding caching policy
optimization problem with known content popularity, whose solution reflects the existing policy
in literature. To focus on the performance gain brought by distinguishing user preference from
content popularity, we consider a simple objective: the offloading gain of D2D communications.
To reduce the time complexity in finding the solution, we provide a local optimal algorithm.
A. System Model
Multiple BSs in the area are connected to core network via backhaul to serve the K uniformly
distributed users, which constitutes a set of users U = {u1 , u2 , ..., uK } that request the files in
content library F. Assume that each file is with same file size, but the results are applicable for
general case with different sizes [7] by dividing each file into chunks of approximately equal
size.1 Each single-antenna user has a local cache to store M files, and can act as a helper to
share files via D2D link. To provide high rate transmission with low energy cost at each user
device, we consider a user-centric D2D communication protocol as in [12]. A helper can serve
as a D2D transmitter and send its cached files to a user only if their distance is smaller than
a collaboration distance rc , which reflects the coverage of the helper. Each BS is aware of the
cached files at and the locations of the users, and coordinates the D2D communications.
1

We can also formulate another optimization problem with different file sizes, which can be shown as a knapsack problem.

January 4, 2018

DRAFT

9

Proactive caching consists of content delivery phase and content placement phase.
In content delivery phase, each user requests files according to its own preference. If a user
can find its requested file in local cache (i.e., fetching locally), it directly retrieves the file with
zero delay. If not, the user sends the request to a BS. If the BS finds that the file is cached in the
local caches of helpers adjacent to the user, it informs the request to the closest helper, and then
a D2D link is established between the user and the closest helper (i.e., fetching via D2D link).
Otherwise, the BS fetches the file via backhaul to serve the user. For simplicity, both fetching
locally and via D2D link are called fetching via D2D links in the sequel.
Denote the file requests matrix after a period as N = (nk,f )K×F (i.e., the user-content matrix),
where nk,f ≥ 0 is the number of requests from uk ∈ U to ff ∈ F. Assume that a central processor
(CP) can record the requests history of users. To predict user preference, the CP needs to be
deployed in the mobile core, such that most requests of users can be recorded. To determine
where to deploy CP, one needs to consider both coverage area and computational cost.
In content placement phase, the CP learns the user preferences Q and active levels w from
the requests history N, and then optimizes the caching policy for users and informs the cached
files of the users to the BSs. We consider deterministic caching policy,2 denoted as a vector
ck = [ck,1 , ck,2 , ..., ck,F ] for the kth user, where ck,f = 1 if ff is cached at uk , ck,f = 0 otherwise,
P
and Ff=1 ck,f ≤ M . Denote the caching policy for all users as C = (ck,f )K×F . After being
informed about the files to be cached at the users in its cell, a BS fetches the files from the core
network and refreshes the caches of the users during the off-peak time, say every several hours,
noticing that traffic load varies on the timescale of hours as measured by real cellular data [21].
Due to user preference similarity, some users may have common contents to precache as shown
later, which can be pre-downloaded by the BS via multicast to reduce wireless traffic.
B. Caching Policy Optimization with Individual Request Behavior
We use offloading probability to reflect the offloading gain introduced by cache-enabled D2D
communications, defined as the probability that a user can fetch the requested file via D2D links,
which represent the average ratio of requests able to be offloaded.
When optimizing caching policy in the content placement phase, it is hard to know where a
mobile user will be located in the content delivery phase. Therefore, it is hard to know when and
2

We do not consider probabilistic caching policy, which is designed under the assumption that a group of nodes share the

same caching distribution [9–14], and hence is not appropriate for a system with heterogeneous user preferences.

January 4, 2018

DRAFT

10

how long the users will contact. Fortunately, data analysis shows that users always periodically
reappear at the same location with high probability [34]. Consequently, it is reasonable to assume
that the contact probability is known a priori [26]. Let A = (ai,j )K×K represent the contact
probability among users, where ai,j ∈ [0, 1] is the probability that the distance between the ith
user and the jth user is less than rc . When all users do not move, ai,j = 0 or 1.
In D2D communications, adjacent helpers may have overlapped coverage. Since different
helpers need to serve different groups of users, which depend not only on rc but also on the
cached files at the adjacent helpers, the “local popularity” observed at a helper differs from that
observed at another helper and relies on the caching policy. As a result, the caching policy can
not be designed based on the “local popularity”.
Denote pdk,f (A, C) as the probability that the kth user can fetch the f th file via D2D links
given contact probability A and caching policy C. The complementary probability of pdk,f (A, C)
is the probability that the f th file is not cached at any users in proximity to the kth user, which
Q
can be derived as K
m=1 (1 − ak,m cm,f ). Then, we can obtain the offloading probability as
!
K
F
K
F
K
Y
X
X
X
X
(1 − ak,m cm,f ) .
qf |k 1 −
wk
qf |k pdk,f (A, C) =
wk
poff (Q, w, A, C) =
k=1

k=1

f =1

m=1

f =1

(7)
With known user preference and active level, the caching policy can be optimized to maximize
the offloading probability by solving the following problem,
P1 :

poff (Q, w, A, C)
PF
f =1 cm,f ≤ M, cm,f ∈ {0, 1}, 1 ≤ m ≤ K, 1 ≤ f ≤ F.

maxcm,f
s.t.

(8a)
(8b)

Remark 2: If all users are with equal active level and equal preference, then (7) becomes
poff (Q, w, A, C) =

1
K

PF

f =1

pf

PK

k=1

pdk,f (A, C) , ppop
off (p, A, C).

(9)

Remark 3: If the collaboration distance rc → ∞, then ak,m = 1, and (7) becomes
! K
!
F
K
F
K
X
Y
X
X
Y
poff (Q, w, A, C) =
1−
(1 − cm,f )
wk qf |k =
1−
(1 − cm,f ) pf .
f =1

m=1

k=1

f =1

m=1

It is easy to show that poff (Q, w, A, C) = ppop
off (p, A, C) in this extreme case where D2D links
can be established between any two users in the area even with heterogeneous user preferences.
If the assumptions in the two remarks hold, then the “local popularity” observed at every
helper will be identical, which is equal to the content popularity of the area with the K users.

January 4, 2018

DRAFT

11

In practice, the assumptions are not true, hence the caching gain from exploiting user preference
differs from exploiting content popularity.
With known content popularity, the caching policy is optimized by maximizing ppop
off (p, A, C)
in (9) under constraint (8b), called problem P2,3 which is actually a special case of P1.
By setting the contact probability ai,j as 1 or 0 (i.e., all users are static), we can obtain a
special case of problem P2, which has the same structure as a NP-hard problem formulated in
[9]. Since P2 is a special case of P1, problem P1 is NP-hard. As a consequence, it is impossible
to find its global optimal solution within polynomial time. By using similar way of proof in [9],
it is not hard to prove that P1 is equivalent to maximizing a submodular function over matroid
constraints. Thus, we can resort to greedy algorithm, which is commonly used to provide a
solution achieving at least

1
2

of the optimal value for such type of problem [35].4

The greedy algorithm starts with zero elements for the caching matrix, i.e., C = (0)K×F .
In each step, the value of one element in C is changed from zero to one with the maximal
incremental caching gain defined as
vC (m, f ) = poff (Q, w, A, C|cm,f =1 ) − poff (Q, w, A, C)


(a) PK
= k=1 wk qf |k pdk,f A,C|cm,f =1 − pdk,f (A, C) ,

(10)

where (a) follows by substituting (7), C is the caching matrix at previous step, and C|cm,f =1 is
the matrix by letting cm,f = 1 in C. The algorithm is summarized in Algorithm 1.
The loops in step 1 of Algorithm 1 take KM iterations, because there are totally KM files
that are possible to be cached at all users. The step 2 for finding the element in C that introduces
the highest incremental caching gain takes at most KF iterations. For each time of computing
vC (m, f ) in (10), the time complexity is O(K 2 ), and thus computing all vC (m, f ) is O(K 3 F ).
Hence the total time complexity for Algorithm 1 is O(KM (KF +K 3 F )) = O(K 2 F M (K 2 +1)),
which is high especially when the numbers of users K and files F are large.
3

The solution of P2 slightly differs from [11, 12], where the future user location is exactly known in [11] and completely

unknown in [12] when optimizing caching policy, where the contact probability is known in P2.
4

The best algorithm with polynomial time complexity for such problem can achieve (1 − 1e ) optimality guarantee, which

is based on continuous greedy process and pipage rounding techniques [36]. However, when K = 100 and F = 3000 in the
considered setting as detailed later, its complexity is O((F K)8 ) = O(6.5 × 1043 ), which is too complex for our problem.

January 4, 2018

DRAFT

12

Algorithm 1 Greedy Algorithm
Input: A; w; Q; Initialize: Caching matrix C = (0)K×F ; Files not cached at the mth user
C¯m ← {f1 , f2 , ..., fF }; Users with residual storage space U0 ← {u1 , u2 , ..., uK };
1:
2:
3:
4:

while U0 6= ∅ do
[m∗ , f ∗ ] = arg maxum ∈U0 ,ff ∈C¯m vC (m, f ); C = C|cm∗ ,f ∗ =1 ; C¯m∗ ← C¯m∗ \ ff ∗ ;
if |C¯m∗ | = F − M then
U0 ← U0 \ um∗ ;

5:

end if

6:

end while

7:

C∗ = C;

Output: Caching matrix C∗ .

C. A Low Complexity Algorithm with 1/2 Optimality Guarantee
Since the greedy algorithm is with high time complexity, finding a low-complexity algorithm is
worthwhile for practice use. In what follows, we propose an alternating optimization algorithm,
which improves the offloading gain at every iteration and converges to a local optimal solution.
To be specific, we fix the caching policy at users cm (m 6= k 0 , 1 ≤ m ≤ K) and optimize ck0 .
Then, from problem P1 we obtain the optimization problem with respect to ck0 as


QK
PF
P
0
0
(1
−
a
c
)(1
−
a
c
)
q
1
−
w
P10 : maxck0 ,f foff (ck0 ) = K
k,m m,f
k,k k ,f
m=1,m6=k0
f =1 f |k
k=1 k
s.t.

PF

f =1 ck0 ,f

≤ M, ck0 ,f ∈ {0, 1}, 1 ≤ f ≤ F.
(11)

Proposition 1: P10 can be solved with polynomial time complexity O(F (K 2 + M )).
Proof: See Appendix A.
Based on the proof of Proposition 1, we propose an algorithm to iteratively solve problem P10
by changing k 0 from 1 to K until convergence. The algorithm starts with a given initial value of
C. In every iteration, by fixing cm (m 6= k 0 , 1 ≤ m ≤ K), it respectively computes the offloading
gain introduced by caching the f th file at the k 0 th user
bk0 ,f =

PK

k=1

wk qf |k ak,k0

QK

m=1,m6=k0 (1

− ak,m cm,f ), 1 ≤ f ≤ F, 1 ≤ k 0 ≤ K.

(12)

Then, the algorithm finds the file indices with the maximal M values of bk0 ,f to constitute a set

January 4, 2018

DRAFT

13

Ik0 , and obtain c∗k0 as
c∗k0 ,f =


 1, f ∈ Ik0


.

(13)

0, f ∈
/ Ik0

The detailed algorithm is presented in Algorithm 2. The loops in step 2 take K iterations. Step 3
is with complexity O(F (K 2 + M )) according to Proposition 1. Hence the total time complexity
of Algorithm 2 is O(tA2 KF (K 2 + M )), where tA2 is the number of iterations for step 1.
Algorithm 2 A Low Complexity Algorithm
Input:
1:
2:

(0)

A; w; Q; Initialize: Random caching cm (1 ≤ m ≤ K), t ← 1;

repeat
for k 0 = 1, 2, ..., K do
(t−1)

3:

Based on cm

4:

ck0 = c∗k0 ;

5:
6:

(m 6= k 0 ), compute bk0 ,f by (12), constitute Ik0 and obtain c∗k0 by (13).

(t)

end for
(t)

(t−1)

until We obtain the converged result (cm = cm

, 1 ≤ m ≤ K)

(t)

Output: Caching matrix cm .

Proposition 2: Algorithm 2 monotonically increases the objective function of problem P1 and
finally converges to achieve at least 1/2 optimality.
Proof: See Appendix B.
It is noteworthy that Algorithm 1 and Algorithm 2 can also solve P2 by letting qf |k = pf , ∀k, f
in Q. Solutions for P1 and P2 obtained with Algorithm 1 are called S1 − A1 and S2 − A1, and
solutions using Algorithm 2 for P1 and P2 are called S1 − A2 and S2 − A2, respectively.
IV. L EARNING U SER P REFERENCE AND ACTIVE L EVEL
In this section, we first use pLSA to model content request behavior of an individual user. We
then learn the model parameters by maximizing likelihood function, either without the pLSA
model for comparison or with the model using the EM algorithm, which is efficient for ML
parameter estimation with latent variables [23]. Finally, we present a prior knowledge based
algorithm to learn user preference.

January 4, 2018

DRAFT

14

A. Modeling Individual User Behavior in Requesting Contents
To characterize the request behavior of a user, pLSA associates each request with a topic,
which may be unobservable but can be intuitively interpreted as comedy, adventure, etc.
By introducing latent topic set Z = {z1 , z2 , ..., zZ } with cardinality |Z| = Z, pLSA associates
each topic zj ∈ Z with each possible user request, i.e., uk ∈ U requests ff ∈ F. Specifically,
the request of each user can be modeled as the following steps with three model parameters:
•
•
•

A request is sent by uk with probability P (uk ) (i.e., active level),
P
uk chooses a topic zj with probability P (zj |uk ) (i.e., topic preference, Zj=1 P (zj |uk ) = 1),
P
uk requests ff in topic zj with probability P (ff |zj ), Ff=1 P (ff |zj ) = 1, where conditional
independence assumption is used. In particular, conditioned on a request being sent by
uk who chooses topic zj , uk chooses ff with probability P (ff |zj , uk ) = P (ff |zj ), i.e.,
P
P (ff |uk ) = zj ∈Z P (ff |zj )P (zj |uk ). In other words, no matter which user sends a request
and selects topic zj , the user will request ff with probability P (ff |zj ).

Then, the joint probability that uk requests ff can be expressed as
P (uk , ff ) = P (uk )P (ff |uk ) = P (uk )

P

zj ∈Z

(14)

P (ff |zj )P (zj |uk ).

B. Learning Individual User Behavior in Requesting Contents
According to maximal likelihood (ML) principle, we can learn P (uk ), P (ff |zj ) and P (zj |uk )
with requests history nk,f by maximizing the following log-likelihood function [37]
X X
X
X X
P
nk,f log P (uk , ff ) =
L = i log P (uiu , fif ) =
nk,f log P (uk )
P (ff |zj )P (zj |uk ),
uk ∈U ff ∈F

uk ∈U ff ∈F

|

{z

}

(a)

|

zj ∈Z

{z

}

(b)

(15)
where the ith sample corresponding to the event that the iu th user requests the if th file, and in
(b) the pLSA model is applied.
1) ML algorithm without pLSA model: By maximizing the log likelihood function in (a) of
(15) without the pLSA model, it is not hard to obtain that
P̂ (uk , ff ) =

PK

k0 =1

nk,f
PF

f =1

nk0 ,f

.

Then, the active level and user preference can be learned as ŵk = P̂ (uk ) =
q̂f |k =

P̂ (uk ,ff )
P̂ (uk )

=

P̂ (uk ,ff )
PF
,
f =1 P̂ (uk ,ff )

(16)
PF

f =1

P̂ (uk , ff ) and

respectively. This algorithm is actually a simple frequency-count

prediction, which can serve as a baseline for learning active level and user preference.

January 4, 2018

DRAFT

15

Remark 4: If we directly predict wk and qf |k using (16), the number of parameters to estimate
is KF . By using the pLSA as in (b) of (15), the number of parameters is reduced from KF
to K + KZ + ZF = Z(K + F ) + K, where K parameters are for learning active level, KZ
parameters are for topic preference, and ZF parameters are for P (ff |zj ). With less number of
parameters to estimate, a learning algorithm can converge more quickly.
2) ML algorithm with pLSA model: To maximize the log-likelihood function in (b) of (15),
we first rewrite the function as
X X
X
X
nk,f log
P (ff |zj )P (zj |uk ),
L=
nk log P (uk ) +
uk ∈U ff ∈F

uk ∈U

{z

|
where nk =

P

ff ∈F

(a)

}

(17)

zj ∈Z

|

{z

}

(b)

nk,f . It is not hard to see that the terms in (a) and (b) can be independently

maximized. The active level of uk can be learned by maximizing term (a) in (17) as
ŵk = P̂ (uk ) =

PK

k0 =1

n
PkF

f =1

nk0 ,f

,

(18)

which is the same as that obtained from (16). The other two model parameters P (ff |zj ) and
P (zj |uk ) can be learned by maximizing term (b) in (17) using the EM algorithm as follows [37].
Starting from randomly generated initial values for the model parameters P (zj |uk ) and P (ff |zj ),
1 ≤ j ≤ Z, 1 ≤ f ≤ F and 1 ≤ k ≤ K, the EM algorithm alternates two steps: expectation
(E) step and maximization (M) step. In the E-step, the posterior probabilities are computed for
latent variable zj with current estimation of the parameters as
P̂ (zj |uk , ff ) =

P

P̂ (zj |uk )P̂ (ff |zj )
,
P̂ (zj 0 |uk )P̂ (ff |zj 0 )

(19)

zj 0 ∈Z

which is the probability that ff requested by uk belongs to topic zj . In the M-step, given
P̂ (zj |uk , ff ) computed by previous E-step, the parameters are updated as
P

P̂ (ff |zj ) =

uk ∈U

P

uk ∈U

P

nk,f P̂ (zj |uk ,ff )

ff 0 ∈F

nk,f 0 P̂ (zj |uk ,ff

P

,
0)

and P̂ (zj |uk ) =

ff ∈F

nk,f P̂ (zj |uk ,ff )
nk

.

(20)

By alternating (19) with (20), the EM algorithm converges to a local maximum of loglikelihood function. Then, the preference of the kth user for the f th file can be learned as
X
q̂f |k = P̂ (ff |uk ) =
P̂ (ff |zj )P̂ (zj |uk ).
(21)
zj ∈Z

January 4, 2018

DRAFT

16

3) Prior Knowledge Based Algorithm to Learn User Preference: Video files in real world
website always have topic information, e.g., movies are labeled with comedy, drama and so on.
Intuitively, the topic preference and active level of a user change slowly over time, and hence
can be regarded as invariant. This will be validated later by real dataset. Thanks to the pLSA
model, such intuition naturally yields a prior knowledge based algorithm to learn user preference
by exploiting the active level and topic preference of a user learned previously during a much
longer time than learning user preference, with the help of the topic information. This algorithm
can be regarded as a parameter-transfer approach [38]. While the active level P (uk ) and topic
preference P (zj |uk ) can never be learned perfectly, we assume that they are known in order to
show the potential of such transfer learning. Then, the user preference can be learned by only
estimating P (ff |zj ), which can be obtained similarly as in (20),
P

uk ∈U nk,f P̂ (zj |uk ,ff )

P
, ff ∈ Fj
P
uk ∈U
ff 0 ∈F nk,f 0 P̂ (zj |uk ,ff 0 )
,
P̂ (ff |zj ) =


0,
ff ∈
/ Fj

(22)

where Fj is the set of files associated with topic zj (1 ≤ j ≤ Z), which is available on the video
website. For instance, the movie Forrest Gump is associated with topics comedy, romance and
war on the MovieLens. The detailed algorithm is presented in Algorithm 3. Step 2 takes KF Z
times computation of posterior probability by (19), where each computation is with complexity
O(Z − 1) and thus totally at most O(KF Z(Z − 1)). Step 3 computes (22) with ZF times, each
is with complexity O(K(F + 1)). It is not hard to see that step 4 is with complexity O(KF Z).
Hence the total time complexity for Algorithm 3 is O(tA3 KF Z(Z + F + 1)), where tA3 is the
number of iterations for step 1.
V. U SER R EQUEST B EHAVIOR A NALYSIS WITH M OVIE L ENS DATASET
The gain from caching highly depends on the user behavior in requesting contents, both
collectively and individually. In this section, we first use a real dataset to analyze the connection
between file catalog size and number of users in a region, as well as the active level, topic
preference of each user and user preference, and validate the intuition in Section IV-B3. Then,
we validate the user preference model provided in Section II.
A. Statistical Results of User Demands
We use the MovieLens 1M Dataset [24] to reflect the request behavior, where MovieLens is
a website that recommends movies for its users operated by GroupLens lab at the University

January 4, 2018

DRAFT

17

Algorithm 3 Learning user preference with prior knowledge.
Input:

N; Z; Fj , 1 ≤ j ≤ Z; P̂ (zj |uk ); Stop condition 0 <  < 1;

Initialize: P̂ (0) (ff |zj ); Step i ← 1; Difference ∆ ← ∞; Log likelihood L(0) ← 0;
1:

while ∆ >  do

2:

Using P̂ (zj |uk ) and P̂ (i−1) (ff |zj ) to compute P̂ (i) (zj |uk , ff ) by (19);

3:

Using P̂ (i) (zj |uk , ff ) and Fj to compute P̂ (i) (ff |zj ) by (22);

4:

Compute log likelihood L(i) with P̂ (zj |uk ) and P̂ (i) (ff |zj ) using term (b) in (17);

5:

∆ = |L(i) − L(i − 1)|; i ← i + 1;

6:
7:

end while
P
q̂f |k ← zj ∈Z P̂ (ff |zj )P̂ (zj |uk ) to compute Q̂;

Output: Q̂.

of Minnesota. This dataset contains 1000209 ratings for 3952 movies provided by 6026 users
from the year of 2000 to 2003. Each sample of the dataset consists of user identity (ID), movie
ID, rating and timestamp. Because users typically give ratings only after watching, we translate
the rating record into the request record, i.e., when a user gives rating for a movie, we set the
movie as requested by once. Except for the ratings, MovieLens also provides topic information
of movies. Every movie is associated with one, two or more topics from 18 topics, which include
action, adventure, animation, children’s, comedy, etc. genre and are denoted as z1 , ..., z18 . For
instance, Forrest Gump is associated with topics comedy (z5 ), romance (z14 ) and war (z17 ). From
the topic information provided by MovieLens, we can see that if the f th movie is not associated
with the jth topic, users who select jth topic will not request the f th file, i.e., we can set
P (ff |zj ) = 0 in (22).
To analyze temporal evolution of user behavior, we sort all the 3952 movies according to their
released date in ascendant order and then divide them into two subsets F1 and F2 , where the
file request matrices on F1 and F2 are N1 ∈ R6040×1976 and N2 ∈ R6040×1976 , respectively. N1
can reflect user behavior on previously released file subset F1 , and N2 can reflect user behavior
on subsequently released file subset F2 . Specifically, we analyze the following statistical results:
•

File catalog size: To reflect the randomness of the users in sending requests, it is the average
number of files requested by a given number of randomly chosen users, which is obtained
from N = [N1 N2 ] and the average is taken over users.

January 4, 2018

DRAFT

18

•

Active level: P1 (uk ) and P2 (uk ) are computed using (18) with N1 and N2 , respectively.

•

Topic preference: Denote the topic preference of the kth user estimated on subsets F1
and F2 as p1 (Z|uk ) = [P1 (z1 |uk ), ..., P1 (zZ |uk )] and p2 (Z|uk ) = [P2 (z1 |uk ), ..., P2 (zZ |uk )],
respectively. P1 (zj |uk ), P2 (zj |uk ) are computed using (20) by EM algorithm with N1 and N2 ,
respectively. To reflect the temporal dynamic of topic preference for the kth user, we use the

•

metric of cosine similarity in (3) to evaluate the similarity level as sim(p1 (Z|uk ), p2 (Z|uk )).
P
User preference: qf |k = zj ∈Z P (ff |zj )P (zj |uk ) is obtained by EM algorithm on N1 . The
result obtained from N2 or N is similar, and hence is omitted for conciseness.

10-2

10-3

Active level (w k)

File catalog size

103

10-4

102
2

Log, a=301, b=53.47, R = 0.86
Power, a=-6379, b=-0.27, c= 4372, R2 =0.97
MovieLens

10-5

Zipf, a=0.0029, -= 0.29, R 2 = 0.93
(Top 1000 users)
Weibull, a=0.0027, b= 0.82, R 2 = 0.99
MovieLens-P 1 (u k ), Based on N1
MovieLens-P 2 (u k ), Based on N2
Exponential, a=0.00088, b= -0.00096, R 2 = 0.92

10

1

100

101

102

103

10

Number of users

-6

100

101

102

103

104

User indices

(a) Connection between file catalog size and number of users

(b) Active levels of different users in descending order

Fig. 1. File catalog size and user active level in log-log coordinates.

In Fig. 1(a), we show the relation between file catalog size and the number of users obtained
from dataset (with legend “MovieLens”) and the fitted curves. The curve with legend “Log” fits
the function f (x) = a log(bx), and the curve with legend “Power” is with f (x) = axb + c. To
evaluate the goodness of fit, we use the coefficient of determination (also called R-square) in
linear regression, i.e., R2 = 1 −
the ith sample, and ȳ =

PS

i=1

S

yi

PS
2
i=1 (yi −f (xi ))
P
,
S
2
i=1 (yi −ȳ)
2

where S is the number of samples, (xi , yi ) is

[39]. R ≤ 1, and the large value of R2 indicates good fitting

result. The parameters a, b and c for each function and R2 are listed in the legends. We can see
that the catalog size first increases quickly and then slowly, where “Power” function fits better
than “Log” function. When the number of users is small (e.g., in a small cell), the catalog size
is small, which implies that the cache hit ratio could be high with limited cache size. However,
with limited number of requests due to a few associated users, the popularity is hard to predict
rapidly at the small BS. When the number of users is large (e.g., in a macro cell), the catalog

January 4, 2018

DRAFT

19

size increases slowly, and both fitted curves are close to the measured catalog size. In [4], the
authors suggest to use logarithm function to compute the catalog size without validation. Here,
the result shows that “Log” is reasonable when the number of users in the considered area is
large, say K ≥ 100, at least for MovieLens dataset.
In Fig. 1(b), we show the active levels of users, where the user indices are ranked in descending
order according to P1 (uk ). We can see that the distribution of active levels is skewed, which
indicates that majority requests are generated by a small number of users. Besides, the distribution
of active levels from the two subsets of data are similar, where the cosine similarity is 0.87. This
validates that the active level of a user changes slightly over time. We also show the corresponding
b

fitted distributions, where “Weibull” is with function f (x) = abxb−1 e−ax , “Exponential” is with
function f (x) = ae−bx , and “Zipf” is with function f (x) = ax−β (shown only for the most active
1000 users). We can see that the curve with the real data is linear on a log-log scale for active
users, but the tail (after the 1000th user) decreases quickly. The truncate tail may come from
the rating behavior of users for watched movies on MovieLens website. Some users rarely give
ratings, and some users do not continuously give ratings. As a result, the observed active levels
of these users are very low. From the values of R2 , we can find that “Weibull” is the best fitted
distribution. Nonetheless, the distribution of the most active 1000 users is very close to Zipf.

0.3

Rerank

P 1 (Z|u 100 )

P 1 (Z|u 10 )

0.2

0.2
0.1

0.2

Topic preference of user 1

Topic preference

0.25

100

0.3

0.3

0.1

0

0
5

10

Topics

15

5
Rerank

10

15

Topics

0.15
User 1:P 1 (Z|u1 )

0.1

User 10:P1 (Z|u10 )
User 100:P 1 (Z|u100)

10-1

10-2

10-3

0.05

MovieLens
Zipf, a =0.31, -=1.05, R2 = 0.99
Exponential, a =0.42, b=0.40, R 2 = 0.92
Weibull, a =0.48, b=0.90, R 2 = 0.92

10-4
0
5

8

1 15 11 16 14 2 17 6 12 3

9 18 13 10 7

100

4

(a) Topic preferences of different users

101

Ranked topic indices

Topic indices

(b) Topic preference of the 1st user in descending order

Fig. 2. Topic preferences of different users and fitted distributions.

In Fig. 2(a), we show the topic preferences of the 1st, 10th and 100th users obtained from
F1 , i.e., p1 (Z|u1 ), p1 (Z|u10 ) and p1 (Z|u100 ). The results obtained from F2 are similar and are
not shown. The labels of x-axis are ranked in descending order according to p1 (Z|u1 ). The
January 4, 2018

DRAFT

20

topic preferences of the 10th and 100th users with re-ranked x-axis according to p1 (Z|u10 ) and
p1 (Z|u100 ) are also provided in the inner-figures. We can see that topic preference of each user is
skewed, which indicates that each user has strong preferences towards specific topics. In fact, the
topic preferences of all users in the dataset are skewed, which is not shown for consciousness.
We can also see that topic preferences of different users differ. For example, the most favorite
topic is comedy for the 1st and 100th user and drama for the 10th user.
In Fig. 2(b), we show the topic preference of the 1st user and the fitted distributions in
a log-log coordinate. We can see that the best fitted distribution is a Zipf distribution with
parameter β = 1.05. We have also fitted distributions of topic preferences for other users, but
the curves are not provided. We observe that the best fitted distributions differ for users, where
Zipf distribution is the best of 1425 users, Weibull distribution is the best for 1899 users, and
Exponential distribution is the best for the remaining 2702 users (but the difference in R2 from
Weibull distribution for these users is negligible). For the users whose best fitted distributions are
Zipf distributions, the parameters of β differ, which approximately follow a uniform distribution
in [0.5, 3]. Yet for the most favorite several topics, Zipf distribution is always the best.

1

10-2

Empirical CDF

0.8

0.6

6
4

10-3

2

User preference

Empirical PDF

8

0
0

0.2

0.4

0.6

0.8

1

Cosine similarity

0.4
Top 1/3 users
Top 2/3 users
All users

0.2

0.2

0.4

0.6

Cosine similarity

0.8

1

Zipf, a=0.0064, - =0.26, R 2 = 0.982
(Top 100 files)
Exponential, a=0.0027,b=0.0028,R2 =0.931

Movielens

10-5

0
0

10-4

10-6
100

Weibull, a=0.0067,b=0.8273, R2 = 0.9925

101

102

103

(a) Empirical CDF and PDF of cosine similarity between (b) User preference of the 1st user, where the files are
p1 (Z|uk ) and p2 (Z|uk ).

ranked in descending order.

Fig. 3. Temporal dynamics of topic preferences and user preference of the 1st user.

In Fig. 3(a), we show the empirical cumulative distribution function (CDF) and probability
density function (PDF) of the cosine similarity between topic preferences over time of all users.
We can see that 60% of all users have cosine similarity larger than 0.8, and almost 90% users
among the top 1/3 active users have cosine similarity larger than 0.8 (i.e., their topic preferences

January 4, 2018

DRAFT

21

change slowly in the three years). Considering that the statistical results for active users with
more requests are with high confidence level, this result indicates that topic preferences can be
approximated as invariant over time.5 This validates the intuition in Section IV-B3.
In Fig. 3(b), we show user preference of the 1st user and the fitted distributions. The user
preference for the top 100 favorite files is close to Zipf distribution (a straight line in the log-log
coordinate), and the preference for less favorite files has a truncated tail. This is because a user
almost does not request the files belonging to its unfavorable topics. We have also fitted the
preferences of other users (but are not shown). We find that Weibull is the best fitted distribution
for all users, but the parameters and the skewness of curves differ. The user preferences for the
top favorable 100 files of each user can be fitted with Zipf distribution, but the parameters of β
differ in a range of [0.2, 0.8]. In summary, the preferences of different users differ in the favorite
file set, skewness, and ranking. This is not consistent with the model that all user preferences are
Zipf distributions with same parameter but with different ranks as assumed in [25, 26]. Besides,
we observe that the average cosine similarity of preferences among different users on dataset N1
is as low as Ek,m [sim(qk , qm )] ≈ 0.4.6 This is mainly because the interested file sets of users
are less overlapped, recalling that the topic preferences of users differ.
B. Validating Synthetic User Preference Model
Now, we validate the user preference model by comparing the results obtained from data
synthesized by the generative process in Section II and those from the MovieLens dataset.
In Fig. 4(a), we first show the impact of parameter α in the kernel function. The inner-figure
indicates that the synthetic user preference model can capture different levels of similarity among
user preferences by adjusting α, while the Zip parameter β has negligible impact on the average
cosine similarity. This seems counter-intuitive, since a more skewed popularity distribution seems
to imply highly correlated user preferences. However, such an intuition comes from the implicit
assumption that the users send their requests with equal probability (i.e., with identical active
level), which is not true in reality. From the figure we can observe that even when β = 1, α can
be as small as 0.1. This is because few users are very active in sending file requests and have
5

In recommendation problem, it has been shown that user preference varies over time due to the dynamic of file catalog and

the user’s exploration for new items [40]. However, the topic preference variation has never been analyzed in the literature.
6

We also analyze a real video dataset of Youku in a university campus. The result shows that Ek,m [sim(qk , qm )] ≈ 0.28.

January 4, 2018

DRAFT

22

10-2

10

10

-3

-4

1
0.8

- = [1,0.5,0]

0.6
0.4

0.4

0.4

0.4

0.3

0.3

p(Z|u 10 )

0.5

Topic Preference

, = 0.1

Average Similarity

Active level w k

10

-1

-=1
-=0.5
-=0

p(Z|u 100 )

0.6

100

0.2
0.1

0.2
0.1

0
5

10

15

0

20

5

Topic indices

10

15

20

Topic indices

0.3
Rerank

Rerank

0.2
User 1: p(Z|u 1 )

0.2

User 10: p(Z|u 10 )

0.1

User 100: p(Z|u 100 )

0
0

0.5

1

,

100

101

102

0
2

4

6

8

10

12

14

16

18

20

Topic indices

User indices

(a) Active levels of users in a log-log coordinate

(b) Topic preferences of users, α = 0.36 and β = 0.6.

Fig. 4. Active level and topic preferences obtained from the requests generated by the synthetic method, K = 100, F = 3000.

skewed user preference, who have large impact on content popularity according to (2). We can
see that the distributions of user active level are skewed, which agree well with the results in
Fig. 1(b) obtained from the MovieLens dataset.
In Fig. 4(b), we show the topic preference of the 1st, 10th and 100th users. The labels of
x-axis are ranked according to p(Z|u1 ), as in Fig. 2(a). We can see that the topic preferences of
the users are skewed, and the topic preferences of the three users are with different distributions,
which are consistent with the results in Fig. 2(a) obtained from the MovieLens dataset.
VI. S IMULATION R ESULTS
In this section, we demonstrate the caching gain by exploiting user preference over content
popularity, either perfect or predicted. Simulation results are obtained from data generated by
the synthetic model in section V-B, which can provide ground truth of the request behavior for
evaluation, and from the MovieLens dataset, which can validate the gain from real data.
We consider a square area with side length 500 m, where K = 100 users are uniformly
located. The collaboration distance rc = 30 m. The file catalog size F = 3000 (obtained from
Fig. 1(a) for 100 users), and each user is willing to cache M = 5 files (i.e., 1.67 ‰ of all
files). α = 0.36 in the kernel function of the synthetic model, which corresponds to the average
cosine similarity 0.4 of the MovieLens dataset (obtained from Fig. 5(a)). The parameter of Zipf
distribution is β = 0.6, which is slightly smaller for a small area than that is observed at the

January 4, 2018

DRAFT

23

Web proxy as reported in [31]. We divide time into two-hour periods, each consisting of a peak
time and an off-peak time.7 The cached files at each user are updated in off-peak time. This
setup is used in the sequel unless otherwise specified.
A. Impact of Key Parameters
In the sequel, we analyze the impact of user mobility, user preference similarity parameter α,
collaboration distance rc , cache size M , and Zipf parameter β on the offloading probability.
We consider a widely used mobility model, random walk model, where a user moves from its
current location to a new location by randomly choosing a direction and speed to travel [41]. To
compute the contact probability matrix, we consider the two-hour period where each user moves
100 seconds before changing direction and speed. The users are initially uniformly distributed,
and the speed and direction of each user are uniformly chosen from [0, vmax ] m/s and [0, 2π],
respectively. By computing the duration that the kth and the mth user can establish D2D links,
tdk,m , in the period of Tp = 2 hours, we can obtain the contact probability ak,m =

tdk,m
.
Tp

By

increasing vmax , users may move with higher speed, and when vmax = 0, all users keep fixed.
In this subsection, both user preference and content popularity are perfect.
In Fig. 5, we show the impact of user mobility. A1 and A2 in the legend respectively represent
the greedy algorithm (i.e., Algorithm 1) and local optimal algorithm (i.e., Algorithm 2), which
achieve almost the same offloading probability. The offloading probabilities decrease slightly with
the growth of vmax , as explained as follows. Owing to the mobility model, the average number
of users that a user can establish D2D links with at any time does not change with vmax . Then,
the total effective cache size seen by the user does not change with vmax . On the other hand,
every user can contact with more users in the period with higher vmax . Then, the caching policy
needs to be optimized by considering the preferences of more users, which reduces the cache
hit ratio due to heterogeneous user preferences. Since the impact of mobility is not significant,
we only consider vmax = 0 in the sequel. To obtain the results of A2 in Fig. 5, three iterations
of step 1 (i.e., tA2 = 3) is necessary for convergence. According to analysis in Section III, the
7

Using other values as the period does not affect the learning performance of user preferences. Yet the period can not be

too short, since a frequent content placement brings extra traffic load. Numerical results under the considered setup show large
opportunity of using multicast for precaching. In particular, (i) only 76 files need to be pre-downloaded to users via unicast
where the other 424 files can be placed to users via multicast, (ii) 20% of the 500 files should be placed at more than 10 users,
and 50% of files should be placed at more than 5 users. Besides, not all the 500 files need to be changed in each update.

January 4, 2018

DRAFT

24

0.14

Offloading Probability

0.12
0.1
S2-A1
S2-A2
S1-A1
S1-A2

0.08
0.06
0.04
0.02
0
0

0.5

1

1.5

2

v max (m/s)

Fig. 5. Impact of user mobility, α = 0.36, S1 is the caching policy with user preference, and S2 is the policy with content
popularity that represents existing caching policy.

time complexity for A1 and A2 are respectively O(K 2 F M (K 2 + 1)) and O(3KF (K 2 + M )),
and A2 will be

KM (K 2 +1)
3(K 2 +M )

≈ 167 times faster than A1 when K = 100 and M = 5. Since the

proposed local optimal algorithm can achieve the same performance and is faster than the greedy
algorithm, we only use A2 to obtain the caching policy in the following.

0.3

0.8
0.7

Offloading Probability

Offloading Probability

0.25
S1, r c = 50 m
S1, r c = 30 m

0.2

S2, r c = 50 m
S2, r c = 30 m

0.15

0.6
S1,M=50
S2,M=50
S1,M=5
S2,M=5

0.5
0.4
0.3
0.2

0.1
0.1
0.05
0.2

0
0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

, in kernel function

(a) Offloading probability vs. α, β = 0.6 and M = 5.

0

0.2

0.4

0.6

0.8

1

Zipf Parameter -

(b) Offloading probability vs. β, α = 0.36 and rc = 30 m.

Fig. 6. The impact of α, β, rc and M , S1 and S2 are caching policies with user preference and content popularity.

In Fig. 6(a), we show the impact of α and rc . We can see that the offloading gain of S1
over S2 is high when α is small. This suggests that optimizing caching policy according to user
preferences is critical when the user preferences are less correlated. As expected, when α → 1,

January 4, 2018

DRAFT

25

the performance of the two policies coincide. The offloading gain is high for large collaboration
distance, but the gain by using S1 reduces as indicated in Remark 3. This is because with the
growth of rc , the number of users whose preferences a helper should consider for optimizing
caching policy increases (when rc → ∞, the number of users equals to K).
In Fig. 6(b), we show the impact of β and M . As expected, with the growth of the value of
M or β, the offloading probabilities increase for both S1 and S2. This is because with a given
value of α, the preference of every user becomes more skewed when β increases.
B. Offloading Gain with Learned User Preference
In what follows, we demonstrate the performance gain of the proposed caching policy by
exploiting user preferences over that with content popularity, and the gain provided by learning
with the pLSA model and the priori knowledge. To this end, we compare the following schemes:
1) “S1-perfect”: The proposed caching policy with perfect user preference and active level,
which is the solution of problem P1.
2) “S2-perfect”: The existing caching policy optimized with perfect content popularity, which
is the solution of problem P2 (slightly different from the policies in [11, 12]).
3) “S1-EM”: The proposed caching policy with ŵ and Q̂ learned by the EM algorithm.
4) “S2-EM”: The existing caching policy with learned local popularity of the K users, which
is computed with (2) from the learned user preference by EM algorithm.
5) “S1-prior”: The proposed caching policy with Q̂ learned by Algorithm 3.
6) “S2-prior”: The existing caching policy with learned local popularity of the K users, which
P
is computed from the learned user preference by Algorithm 3 as p̂f = uk ∈U P̂ (uk , ff ).
7) “S1-baseline”: The proposed caching policy with learned user preference, which is obtained
by the ML algorithm without pLSA model.
8) “S2-baseline”: The existing caching policy with learned local popularity of the K users,
which is obtained by using the traditional frequency-count popularity prediction method in
[16]. Such a popularity learning method is the same as the method used in [17].
In Fig. 7, we show the offloading probability achieved by these schemes during the learning
procedure with the synthetic data. To compare with the results to be obtained with realistic
dataset in the sequel, we set the x-axis as the accumulated number of requests. When the
request arrival rate of the users in the area is 0.04 requests per second, which reflects the
high traffic load scenario for files with 30 MBytes size (typical size of the YouTube videos)

January 4, 2018

DRAFT

26

0.4

0.1

S1-perfect
S1-prior
S1-EM
S1-baseline
S2-perfect
S2-prior
S2-EM
S2-baseline

0.05

0
0

40

80

Number of Accumulated Requests

(a) M = 5.

120

Offloading Probability

Offloading Probability

0.15

0.3

0.2

S1-perfect
S1-prior
S1-EM
S1-baseline
S2-perfect
S2-prior
S2-EM
S2-baseline

0.1

0
0

40

80

120

Number of Accumulated Requests

(b) M = 50.

Fig. 7. Convergence performance on synthetic dataset, α = 0.36, rc = 30 m, Z = 20 for pLSA.

in [42], the accumulated 40, 80 and 120 requests correspond to 22.8, 55.6, and 83.3 hours,
respectively. It is shown that using pLSA and even the priori information do not help accelerate
convergence of local popularity, because the simple frequency-count method already converges
rapidly. Compared to the proposed caching policy with learned user preference (S1-EM, S1-prior
and S1-baseline), S2 with learned local popularity (S2-EM, S2-prior and S2-baseline) converge
to S2 with perfect content popularity (S2-perfect) more quickly. This is because the number
of requests for each file from each user is much less than that from all the users in the area.
Nonetheless, the proposed caching policy with learned user preference can quickly achieve higher
offloading probability than S2 with learned (and even perfect) content popularity. The proposed
caching policy with pLSA (both S1-EM and S1-prior) is superior to the baseline (S1-baseline),
especially when the cache size at each user M is large. This is because some unpopular files
will be cached with large M . For the unpopular files, the number of accumulated requests is
less and user preference learning is more difficult. Besides, we can see that by exploiting prior
knowledge of user active level and topic preference, S1-prior converges much faster than S1-EM.
In Fig. 8, we show the offloading gain with the MovieLens dataset. Because S2-EM and S2prior perform closely to S2-baseline, we only simulate S2-baseline here. We randomly choose
100 users from the dataset (which includes both active and inactive users) and the most popular
3000 files. The timestamps of user requests are shuffled as in [18] to ensure the training set has
the same user demand statistics as the test set. Compared with Fig. 7(a), we can see that the

January 4, 2018

DRAFT

27

0.03
S1-prior
S1-EM
S2-baseline
S1-baseline

0.025
0.02
0.015
0.01
0.005
0
0

50

100

150

200

250

Number of Accumulated Requests

Fig. 8. Offloading probability on MovieLens dataset, rc = 30 m, M = 5.

offloading probabilities for all methods on the realistic dataset are less than those with synthetic
data. This is because a user requests each movie at most once in the realistic dataset translated
from rating data, while a user may request a file more than one time in the synthetic data. In
practice, a user may request a file more than once, e.g., the file is a favorite song of the user or
an educational video. Nonetheless, we can see that the proposed caching policy with predicted
user preference still achieves much higher offloading gain than existing scheme. Because the
prior knowledge of topic preferences is learned on realistic dataset in Fig. 8 rather than perfectly
known as in Fig. 7(a), the performance gain of S1-prior over S1-EM is lower here, which however
is still remarkable. Besides, we can see that S1-baseline always performs the worst, because user
preference for unvisited files is hard to predict by using the ML algorithm without pLSA model
when each user only requests a file at most once. However, we can still predict user preference
for the unvisited files with both S2-EM and S2-prior, owing to the pLSA model.
VII. C ONCLUSIONS
In this paper, we demonstrated the caching gain by exploiting learned individual user behavior
in sending request. We first showed the connection between user preference and content popularity, and provided a probabilistic model to synthesize user preference from content popularity.
We then formulated an optimization problem with given user preference and active level to
maximize the offloading probability for cache-enabled D2D communications. Since the problem
is NP-hard, a low-complexity algorithm achieving at least 1/2 optimality was proposed to solve
the problem. Next, we modeled the user request behavior by pLSA, based on which the EM

January 4, 2018

DRAFT

28

algorithm was used to learn the user preference and active level. We used a Movielens dataset
to analyze several kind of user behavior in requesting contents, and validated the synthetical
model. We find that: (i) when the number of users K in an area is large, the file catalog size
is a logarithm function of K, (ii) the active level of the most active users can be modeled as
Zipf distribution, (iii) the preferences for the most favorable files of each user can be modeled
as Zipf distribution, but with different skewness parameters and different file sets, (iv) the user
preferences are less similar, and (v) the active level and topic preference of each user change
slowly over time, say in the time scale of year. Based on the 5th observation from the real dataset,
we introduced a prior knowledge based algorithm to exploit the active level and topic preference
previously learned, which shows the potential of transfer learning. Simulation results showed
that using pLSA can quickly learn the individual user behavior, and the prior knowledge based
algorithm converges even faster. Compared to existing caching policy using content popularity,
the performance can be remarkably improved by the caching policy exploiting user preferences,
both on the synthetic data with parameters fitted from real dataset and on the MovieLens dataset.
A PPENDIX A
P ROOF OF P ROPOSITION 1
The objective function of problem P10 can be further derived as


QK
PF
P
0
0
(1
−
a
c
)(1
−
a
c
)
q
1
−
w
foff (ck0 ) = K
0
k,m m,f
k,k k ,f
m=1,m6=k
f =1 f |k
k=1 k
=1−

F X
K
X

wk qf |k

(1 − ak,m cm,f )

m=1,m6=k0

f =1 k=1

{z

|
+

K
Y

K
X

PF

f =1 ck0 ,f

k=1

|

wk qf |k ak,k0

(A.1)

}

(a)
K
Y

!
(1 − ak,m cm,f ) ,

m=1,m6=k0

{z
(b)

}

where both terms in (a) and (b) are not related to ck0 ,f . Then, solving the problem in (11) is
equivalent to solving the following problem
P
 (a) P
PF
QK
K
F
0
P1 maxck0 ,f
f =1 ck0 ,f
k=1 wk qf |k ak,k0
m=1,m6=k0 (1 − ak,m cm,f ) =
f =1 ck0 ,f bk0 ,f
s.t.

PF

f =1 ck0 ,f

≤ M, ck0 ,f ∈ {0, 1}, 1 ≤ f ≤ F,
(A.2)

January 4, 2018

DRAFT

29

where (a) is obtained by letting bk0 ,f =

PK

k=1

wk qf |k ak,k0

QK

m=1,m6=k0 (1

− ak,m cm,f ). By finding

file indices of the maximal M values of bk0 ,f (1 ≤ f ≤ F ) to constitute the set Ik0 , it is not hard
to show that the optimal caching policy c∗k0 ,f can be obtained as (13).
To obtain c∗k0 ,f , we need to compute bk0 ,f with time complexity O(K 2 F ) and then choose the
maximal M values of bk0 ,f with complexity O(F M ). Finally, we can prove that the optimal
solution of problem (11) can be obtained with complexity O(K 2 F + F M ) = O(F (K 2 + M )).
A PPENDIX B
P ROOF OF P ROPOSITION 2
(t−1)

Denote the caching policy at the k 0 th user after the (t − 1)th iteration as ck0

. In the tth

(t−1)

) as in (A.1).

iteration, the offloading probability before step 3 of Algorithm 2 is foff (ck0
After that step,

(t)
ck0

is computed for the k 0 th user and the corresponding offloading probability

(t)

(t−1)

is foff (ck0 ). By subtracting foff (ck0
(t)

(t−1)

foff (ck0 ) − foff (ck0

(t)

) from foff (ck0 ), we can obtain



QK
(t)
0
(1
−
a
c
)(1
−
a
c
)
q
1
−
k,m m,f
k,k k0 ,f
m=1,m6=k0
f =1 f |k


QK
PF
P
(t−1)
0
q
1
−
(1
−
a
c
)(1
−
a
c
)
w
− K
k,m m,f
k,k k0 ,f
m=1,m6=k0
f =1 f |k
k=1 k

)=

PK

(a)

PF

=

(b)

k=1 wk

PF

(t)
f =1 ck0 ,f bk0 ,f

= (maxck0 ,f

−

(t−1)
f =1 ck0 ,f bk0 ,f

PF

PF

f =1 ck0 ,f bk0 ,f )

−

(t−1)
f =1 ck0 ,f bk0 ,f

PF

≥ 0,
(B.1)

where (a) is obtained by substituting (12) and (A.1), and (b) is obtained from (A.2). Thus, the
offloading gain is monotonically improved until convergence.
To prove the optimality guarantee of the local optimal algorithm, we first convert the offloading
probability into a function of a set instead of a matrix (i.e., C). Denoting ffk as an action that
caching the f th file at the kth user. Recall that ck,f = 1 represents the kth user caching the f th
file. Then, the caching policy for the kth user, ck = [ck,1 , ck,2 , ..., ck,F ], can be re-expressed as a
set Ck = {ffk |ck,f = 1}, i.e., caching which files at the kth user. Let C = {C1 , C2 , ..., CK }, then
problem P1 is equivalent to the following problem,


P
PF
Q
maxC f(C) = K
w
q
1
−
(1
−
a
)
m
k
k,m
f
|k
k=1
f =1
f ∈C
f

s.t.

(B.2)

|Ck | ≤ M, 1 ≤ k ≤ K.

By defining a set S = {f11 , f21 , ..., fF1 , ..., f1K , f2K , ..., fFK }, we can see that C ⊆ S and f(C) :
0

2S → R is a discrete set function on subsets of S. Let A, B ⊆ S, A ⊆ B, and fkf0 ∈ S \ B.
January 4, 2018

DRAFT

30

∗
Denote the global optimal caching policy as C ∗ = {C1∗ , C2∗ , ..., CK
}, a local optimal caching
L
policy obtained by Algorithm 2 as C L = {C1L , C2L , ..., CK
}, and caching policy at users except
L
L
L
, Ck+1
, .., CK
the kth user as C¯kL = {C1L , C2L , ., Ck−1
}. Then, we can obtain
(a)

(b)

f (C ∗ ) − f (C L ) ≤ f (C ∗ ∪ C L ) − f (C L ) , fC L (C ∗ ) ≤
(c)

≤

PK

∗
k=1 fC¯kL (Ck )

(d)

≤

PK

L
k=1 fC¯kL (Ck )

(e)

≤

f (C1L )

+

PK

k=1

PK

fC L (Ck∗ )

L
L (Ck )
k=2 f∪k−1
i=1 Ci

(B.3)
L

= f (C ),

where (a) is obtained because offloading probability is a monotone increasing function, i.e.,
f (C ∗ ) ≤ f (C ∗ ∪C L ), (b) is obtained by the property that for set A, B, C ⊆ S, we have fA (B∪C) ≤
fA (B) + fA (C), (c) and (e) are obtained by the property that for set C ⊆ A ⊆ S and B ⊆ S,
fA (B) ≤ fC (B), and (d) is obtained because for any caching policy at the kth user denoted as
C a , we have f ¯L (C L ) − f ¯L (C a ) = f (C L ∪ C¯L ) − f (C a ∪ C¯L ) ≥ 0 considering C L is the local
k

Ck

k

Ck

k

k

k

k

optimum of Algorithm 2. Thus, we have f (C L ) ≥

1
f (C ∗ ),
2

k

and Proposition 2 follows.

R EFERENCES
[1] B. Chen and C. Yang, “Caching policy optimization for D2D communications by learning user preference,” in Proc. IEEE
VTC Spring, 2017.
[2] E. Bastug, M. Bennis, and M. Debbah, “Living on the edge: The role of proactive caching in 5G wireless networks,” IEEE
Commun. Mag., vol. 52, no. 8, pp. 82–89, 2014.
[3] K. Wang, Z. Chen, and H. Liu, “Push-based wireless converged networks for massive multimedia content delivery,” IEEE
Trans. Wireless Commun., vol. 13, no. 5, pp. 2894–2905, 2014.
[4] D. Liu, B. Chen, C. Yang, and A. F. Molisch, “Caching at the wireless edge: design aspects, challenges, and future
directions,” IEEE Commun. Mag., vol. 54, no. 9, pp. 22–28, 2016.
[5] N. Golrezaei, P. Mansourifard, A. Molisch, and A. Dimakis, “Base-station assisted device-to-device communications for
high-throughput wireless video networks,” IEEE Trans. Wireless Commun., vol. 13, no. 7, pp. 3665–3676, 2014.
[6] D. Liu and C. Yang, “Energy efficiency of downlink networks with caching at base stations,” IEEE J. Sel. Areas Commun.,
vol. 34, no. 4, pp. 907–922, 2016.
[7] M. Leconte, G. Paschos, L. Gkatzikis, M. Draief, S. Vassilaras, and S. Chouvardas, “Placing dynamic content in caches
with small population,” in Proc. IEEE INFOCOM, 2016.
[8] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE Trans. Inf. Theory, vol. 60, no. 5, pp. 2856–2867,
2014.
[9] N. Golrezaei, K. Shanmugam, A. G. Dimakis, A. F. Molisch, and G. Caire, “Femtocaching: Wireless video content delivery
through distributed caching helpers,” in Proc. IEEE INFOCOM, 2012.
[10] B. Blaszczyszyn and A. Giovanidis, “Optimal geographic caching in cellular networks,” in Proc. IEEE ICC, 2015.
[11] M. Ji, G. Caire, and A. Molisch, “Wireless device-to-device caching networks: Basic principles and system performance,”
IEEE J. Sel. Areas Commun., vol. 34, no. 1, pp. 176–189, 2016.
[12] B. Chen, C. Yang, and A. F. Molisch, “Cache-enabled device-to-device communications: Offloading gain and energy cost,”
IEEE Trans. Wireless Commun., vol. 16, no. 7, pp. 4519–4536, 2017.

January 4, 2018

DRAFT

31

[13] X. Xu and M. Tao, “Modeling, analysis, and optimization of coded caching in small-cell networks,” IEEE Trans. Commun.,
vol. 65, no. 8, pp. 3415–3428, 2017.
[14] Y. Guo, L. Duan, and R. Zhang, “Cooperative local caching under heterogeneous file preferences,” IEEE Trans. Commun.,
vol. 65, no. 1, pp. 444–457, 2017.
[15] A. Gharaibeh, A. Khreishah, B. Ji, and M. Ayyash, “A provably efficient online collaborative caching algorithm for
multicell-coordinated systems,” IEEE Trans. on Mobile Comput., vol. 15, no. 8, pp. 1863–1876, 2016.
[16] A. Tatar, M. D. de Amorim, S. Fdida, and P. Antoniadis, “A survey on predicting the popularity of web content,” Springer
J. Internet Services and Appl., vol. 5, no. 1, pp. 1–20, 2014.
[17] P. Blasco and D. Gunduz, “Learning-based optimization of cache content in a small cell base station,” in Proc. IEEE ICC,
2014.
[18] E. Baştuğ, M. Bennis, E. Zeydan, M. A. Kader, I. A. Karatepe, A. S. Er, and M. Debbah, “Big data meets telcos: A
proactive caching perspective,” IEEE J. Commun. Netw., vol. 17, no. 6, pp. 549–557, 2015.
[19] M. D. Ekstrand, J. T. Riedl, and J. A. Konstan, “Collaborative filtering recommender systems,” Foundations and Trends
in Human-Computer Interaction, vol. 4, no. 2, pp. 81–173, 2011.
[20] D. Jannach, P. Resnick, A. Tuzhilin, and M. Zanker, “Recommender systems–beyond matrix completion,” Communications
of the ACM, vol. 59, no. 11, pp. 94–102, 2016.
[21] U. Paul, A. P. Subramanian, M. M. Buddhikot, and S. R. Das, “Understanding traffic dynamics in cellular data networks,”
in Proc. IEEE INFOCOM, 2011.
[22] T. Hofmann, “Probabilistic latent semantic analysis,” in Proceedings of the Fifteenth conference on Uncertainty in artificial
intelligence, 1999.
[23] A. P. Dempster, N. M. Laird, and D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” J.
Royal Statist. Soc. B, 1977.
[24] F. M. Harper and J. A. Konstan, “The movielens datasets: History and context,” ACM Transactions on Interactive Intelligent
Systems (TiiS), vol. 5, no. 4, p. 19, 2016.
[25] X. Zhang, Y. Wang, R. Sun, and D. Wang, “Clustered device-to-device caching based on file preferences,” in Proc. IEEE
PIMRC, 2016.
[26] Y. Wu, S. Yao, Y. Yang, Z. Hu, and C.-X. Wang, “Semigradient-based cooperative caching algorithm for mobile social
networks,” in Proc. IEEE GLOBECOM, 2016.
[27] E. Bastug, J.-L. Guénégo, and M. Debbah, “Proactive small cell networks,” in Proc. IEEE ICT, 2013.
[28] Y. Shi, M. Larson, and A. Hanjalic, “Collaborative filtering beyond the user-item matrix: A survey of the state of the art
and future challenges,” ACM Computing Surveys, vol. 47, no. 1, p. 3, 2014.
[29] D. M. Blei, A. Y. Ng, and M. I. Jordan, “Latent dirichlet allocation,” JMLR, vol. 3, pp. 993–1022, 2003.
[30] T. Hofmann, “Latent semantic models for collaborative filtering,” ACM Trans. Inf. Syst., vol. 22, no. 1, pp. 89–115, 2004.
[31] P. Gill, M. Arlitt, Z. Li, and A. Mahanti, “Youtube traffic characterization: a view from the edge,” in Proc. ACM SIGCOMM,
2007.
[32] M. Cha, H. Kwak, P. Rodriguez, Y.-Y. Ahn, and S. Moon, “I tube, you tube, everybody tubes: analyzing the world’s largest
user generated content video system,” in Proc. ACM SIGCOMM, 2007.
[33] C. Wang and D. M. Blei., “Collaborative topic modeling for recommending scientific articles,” in Proc. KDD, 2011.
[34] W. j. Hsu, T. Spyropoulos, K. Psounis, and A. Helmy, “Modeling time-variant user mobility in wireless mobile networks,”
in Proc. IEEE INFOCOM, 2007.
[35] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions,”
Mathematical Programming, vol. 14, no. 1, pp. 265–294, 1978.

January 4, 2018

DRAFT

32

[36] G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák, “Maximizing a monotone submodular function subject to a matroid
constraint,” SIAM Journal on Computing, vol. 40, no. 6, pp. 1740–1766, 2011.
[37] T. Hofmann, “Unsupervised learning by probabilistic latent semantic analysis,” Machine learning, vol. 42, no. 1, pp.
177–196, 2001.
[38] S. J. Pan and Q. Yang, “A survey on transfer learning,” IEEE Transactions on Knowledge and Data Engineering, vol. 22,
no. 10, pp. 1345–1359, 2010.
[39] K. S. Trivedi, Probability and Statistics With Reliability, Queuing and Computer Science Applications.

John Wiley and

Sons Ltd., 2002.
[40] D. Rafailidis and A. Nanopoulos, “Modeling users preference dynamics and side information in recommender systems,”
IEEE Trans. Syst., Man, Cybern., Syst., vol. 46, no. 6, pp. 782–792, 2016.
[41] T. Camp, J. Boleng, and V. Davies, “A survey of mobility models for ad hoc network research,” Wiley Online Library
Wireless commun. and mobile comput., vol. 2, no. 5, pp. 483–502, 2002.
[42] 3GPP, “TR 36.814 technical specification group radio access network,” 2014.

January 4, 2018

DRAFT

