A Novel Framework for Coded Caching via Cartesian Product with Reduced Subpacketization
Jinyu Wang, Minquan Cheng, Kai Wan, Giuseppe Caire · 2022 IEEE International Symposium on Information Theory (ISIT) · 2022
Caching is an efficient technique to reduce the peak-time traffic by prefetching some library content at users’ memories during the off-peak hours. Maddah-Ali and Niesen (MN) proposed the first coded caching scheme, which achieves a multicasting gain over the conventional uncoded caching. However, its high subpacketization makes it impractical. In order to reduce the subpacketization while retaining the multicast opportunities, Yan et al. proposed a combinatorial structure called placement delivery array (PDA) to design coded caching schemes. In this paper, we propose a new framework for constructing a PDA for mK1users, by taking the m-fold Cartesian product of a PDA for K1users. By applying the proposed framework to the MN scheme, a new coded caching scheme is obtained, which works for any number of users and any memory regime. While reducing the coded caching gain by only one, the needed subpacketization is at most $O\left( {\sqrt {\frac{K}{q}} {2^{ - \frac{K}{q}}}} \right)$ of that of the MN scheme, where K is the number of users, 0 < z/q < 1 is the memory ratio of each user, and q, z are coprime.