Technical Program

Paper Detail

Paper Title On Coded Caching with Correlated Files
Paper IdentifierTU1.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.