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 loadR. An important parameter in these constructions is the subpacketizationF, 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 requireFto grow exponentially with the number of usersK. In practice, files have finite size and too largeFyields impractically small subpackets. Therefore, it is important to design coded caching schemes withFandRas small as possible. At present, the few known schemes with subpacketization linear inKachieve large load. In this paper, we consider the linear scaling regimeF = O(K)and design schemes with a lower transmission loadR. 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 withK = O(F). 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.

Coded caching is a promising technique to effectively reduce peak traffic by using local caches and the multicast gains generated by these local caches. We aim to design a coded caching scheme to minimize subpacketization$F$and transmission load$R$, since these two metrics are key measures of scheme implementation complexity and transmission efficiency, respectively. In this paper, we focus on studying linear subpacketization coded caching schemes with low transmission load. We first introduce a new combinatorial structure, called non-half-sum disjoint packing (NHSDP), which can be used to construct coded caching schemes where the number of users is equal to the subpacketization, i.e.$K=F$. Then by constructing NHSDPs, we obtain a new class of coded caching schemes which achieve lower load compared to the existing schemes with linear subpacketization and even some of the existing schemes with polynomial subpacketization. Moreover, the novel concept of NHSDPs is closely related to the classical combinatorial structures, including cyclic difference packing, non-three-term arithmetic progressions, and perfect hash family.

Ina$(K, M, N)$coded caching scheme, in order to pursue a low broadcasting rate based on the designed placements at each user's cache we have to divide each file stored in the server into certain packets. However, the implementation complexity of this scheme increases with the number of packets. So it is important to design a scheme with a small subpacketization level and a relatively low transmission load. Placement delivery array (PDA) is a powerful combinatorial structure to characterize the coded caching scheme including the subpacketization and transmission load under uncoded placement. In this paper, using the projective geometry PG$(q,n)$for any prime power$q$and positive integer$n \geq 3$, we propose a novel class of coded caching scheme with polynomial subpacketization which is less than$K^{\lceil\frac{n+2}{t}\rceil-1}$. In addition, when$t=2$, our scheme has$K=\frac{q^{n}-1}{q-1}, M/N < \frac{2}{q}$and subpacketization$F < K^{2}$. Compared to the - optimal schemes under uncoded placement which have the subpacketization exponentially increasing with$K$, our load increases at most$\frac{K}{2 q\binom{n+1}{2}}$times; compared to the existing schemes with low subpacketizations our schemes have also advantages on the subpacketization and load.