主题：Data caching in Next Generation Data Services

嘉宾：张涌  中国科学院深圳先进技术研究院 研究员

时间：2022年2月22日 上午10:00 – 11:00

地点：腾讯会议 （ID：375-449-230）

投影：华中科技大学东五楼210学术报告厅

报告摘要：

Data caching in the cloud is an efficient way to improve the QoS of diverse data applications. However, this benefit is not freely available, given monetary cost to manage the caches in the cloud. In this paper, we study the data caching problem in the cloud that is driven by the monetary cost reduction, instead of the hit rate under limited capacity as in traditional cases. In particular, given a stream of requests R to a shared data item, we present a shortest-path based optimal algorithm that can minimize the total transfer and caching costs within O(mn) time for off-line case, here m represents the number of nodes in the network, while n is the length of the request stream. The cost model in this computation is semi- homogeneous, which indicates that all pairs of nodes have the same transfer cost, but each cache server node has its own caching cost rate. Our off-line algorithm improves the previous results not only in reducing the time complexity from O(m²n) to O(mn), but also in relaxing the cost model to be semi- homogeneous, rendering the algorithm more practical in reality. Furthermore, we also study this problem in its online form, and by extending an anticipatory caching idea, we propose a 2-competitive online algorithm based on the same cost model and show its tightness by giving a lower bound of the competitive ratio as 2-o(1) for any deterministic online algorithm. We provably achieve these results with our deep insights into the problem and careful analysis of the solution algorithms, together with a simulation-based study.

报告人简介：

张涌，中国科学院深圳先进技术研究院研究员，香港大学名誉教授。中国运筹学会数学规划分会理事，中国计算机学会理论专委会委员。2007年博士毕业于复旦大学计算机系。之后在德国柏林工业大学数学系做博士后，香港大学计算机系任职高级研究员。张涌博士的研究方向包括算法优化、分布式计算等，近年来在本领域中国际知名会议和期刊上发表文章超过100 篇。张涌博士近年来承担了多项国家和省部级科研项目，包括国家自然科学基金，科技部国家重点研发计划，中科院重点部署项目等。