A New Construction Structure on Coded Caching with Linear Subpacketization: Non-Half-Sum Disjoint Packing

Abstract

Coded caching is a promising technique for effectively reducing peak traffic by using local caches and the multicast gains generated by these local caches. Coded caching schemes have been widely investigated, following the seminal work of Maddah-Ali and Niesen. Explicit coding constructions have been proposed for a variety of network topologies with information-theoretically optimal or near-optimal transmission load <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</i>. An important parameter in these constructions is the subpacketization <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">F</i>, i.e., the number of subpackets that each content file needs to be divided into. In particular, the original scheme of Maddah-Ali and Niesen as well as several other variants require <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">F</i> to grow exponentially with the number of users <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i>. In practice, files have finite size and too large <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">F</i> yields impractically small subpackets. Therefore, it is important to design coded caching schemes with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">F</i> and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</i> as small as possible. At present, the few known schemes with subpacketization linear in <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> achieve large load. In this paper, we consider the linear scaling regime <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">F = O(K)</i> and design schemes with a lower transmission load <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</i>. Specifically, we first introduce a new combinatorial structure called non-half-sum disjoint packing (NHSDP) which can be used to generate a coded caching scheme with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K = O(F)</i>. A class of new schemes is then obtained by constructing NHSDP. Theoretical analysis and numerical results demonstrate that (i) in comparison to existing schemes with linear subpacketization, the proposed scheme achieves a lower load; (ii) the proposed scheme also attains a lower load than some existing schemes with polynomial subpacketization in some cases; and (iii) the proposed scheme achieves load values comparable to those of existing schemes with exponential subpacketization in some cases. Furthermore, the newly introduced concept of NHSDP is closely related to classical combinatorial structures, including cyclic difference packings (CDP), non-three-term arithmetic progressions (NTAP), and perfect hash families (PHF). These relationships underscore the significance of NHSDP as a combinatorial structure of independent interest in the field of combinatorial design, even beyond its application to coded caching.