| Paper Title |
On Coded Caching with Correlated Files |
| Paper Identifier | TU1.R1.4 |
|---|
| Authors |
Kai Wan, Technische Universität Berlin, Germany; Daniela Tuninetti, University of Illinois at Chicago, United States; Mingyue Ji, University of Utah, United States; Giuseppe Caire, Technische Universität Berlin, Germany |
| Session |
Coded Caching II |
| Location |
Le Théatre (Parterre), Level -1 |
| Session Time |
Tuesday, 09 July, 09:50 - 11:10 |
| Presentation Time |
Tuesday, 09 July, 10:50 - 11:10 |
| Manuscript |
Click here to download the manuscript |
| Abstract
| 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 \in [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 \leq 2$ or $KrM/N \geq K-1$, and (iii) large or small correlation, namely $r \in \{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. |
