On Coded Caching with Correlated Files
Kai Wan, Daniela Tuninetti, Mingyue Ji, Giuseppe Caire · 2019
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.