Paper Info
Title
DP_Greedy: A Two-Phase Caching Algorithm for Mobile Cloud Services
Abstract
In this paper, we study the data caching problem in mobile cloud environment where multiple correlated data items could be packed and migrated to serve a predefined sequence of requests. By leveraging the spatial and temporal trajectory of requests, we propose a two-phase caching algorithm. We first investigate the correlation between data items to determine whether or not two data items could be packed to transfer, and then combine an existing dynamic programming (DP)-based algorithm and a greedy strategy to design a two-phase algorithm, named DP_Greedy, for effectively caching these shared data items to serve a predefined sequence of requests. Under homogeneous cost model, we prove the proposed algorithm is at most 2/α times worse than the optimal one in terms of the total service cost, where α is the defined discount factor, and also show that the algorithm can achieve this results within O(mn <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) time and O(mn) space complexity for m caches to serve a n-length sequence. We evaluate our algorithm by effectively implementing it and comparing it with the non-packing case, the result show the proposed DP_Greedy algorithm not only presents excellent performances but is also more in line with the actual situation.
Year
DOI
Venue
2019
10.1109/CLUSTER.2019.8891031
2019 IEEE International Conference on Cluster Computing (CLUSTER)
Keywords
Field
DocType
data caching,data correlations,mobile cloud computing,dynamic programming,greedy strategy,approximation ratio
Data modeling,Approximation algorithm,Dynamic programming,Computer science,Server,Algorithm,Greedy algorithm,Schedule,Trajectory,Cloud computing
Conference
ISSN
ISBN
Citations 
1552-5244
978-1-7281-4735-2
0
PageRank 
References 
Authors
0.34
11
5
Name
Order
Citations
PageRank
Dong Huang100.34
Xiaopeng Fan259769.90
Yang Wang34010.41
Shuibing He410920.45
Z. Chen53443271.62