On Coded Caching with Correlated Files

This paper studies the fundamental limits of the shared-link caching problem with correlated files, where a server with a library of N files communicates with K users who can store M files. Given an integer r G ∈ [N], correlation is modelled as follows: each r–subset of files contains one and one only common block. The tradeoff between the cache size and the average transmitted load is considered. First, a converse bound under the constraint of uncoded cache placement (i.e., each user directly caches a subset of the library bits) is derived. Then, an interference alignment scheme is proposed. The proposed scheme achieves the optimal average load under uncoded cache placement to within a factor of 2 in general, and it is exactly optimal for (i) users demand distinct files, (ii) large or small cache size, namely KrM/N ≤ 2 or KrM/N ≥ K – 1, and (iii) large or small correlation, namely r ∈{1, 2, N – 1, N}. As a by-product, the proposed scheme reduces the (worst-case or average) load of existing schemes for the caching problem with multi-requests.

本文研究了具有相关文件的共享链路缓存问题的基本极限，其中一个拥有$N$个文件库的服务器与$K$个可存储$M$个文件的用户进行通信。给定一个整数$r_G\in[N]$，相关性建模如下：每个$r$子集的文件包含且仅包含一个公共块。考虑了缓存大小和平均传输负载之间的权衡。首先，推导了在无编码缓存放置约束下（即每个用户直接缓存库比特的一个子集）的逆界。然后，提出了一种干扰对齐方案。所提出的方案在无编码缓存放置情况下，一般能在2倍因子范围内实现最优平均负载，并且对于以下情况是完全最优的：(i)用户需求不同的文件；(ii)缓存大小较大或较小，即$KrM/N\leq2$或$KrM/N\geq K - 1$；(iii)相关性较大或较小，即$r\in\{1,2,N - 1,N\}$。作为一个副产品，所提出的方案降低了现有多请求缓存问题方案的（最坏情况或平均）负载。