I Introduction
Caching is a popular technique to reduce peak traffic rate for large scalar content delivery over networks. The basic idea is to allocate fractions of the contents to user memories during the off peak traffic times, which can be used to help to serve user requests during the peak hours and hence reduce network traffic. Traditional duplicationbased caching schemes focused on exploiting the popularity or statistics of the user demands e.g., see [1]. Coded caching was first proposed in [2], and was shown to be able to significantly reduce network traffic.
The caching system considered in [2] consists of one server connected by users through a shared, errorfree link. The server has a database of files of equal size, and at certain times each user may demand a specific file from the server. It is assumed that each user has a cache that allows it to store fraction of all the files in the server. A centralized coded caching scheme works in two separated phases: the placement phase and the delivery phase. In the placement phase, the server, without any knowledge of the user demands, allocates certain uncoded packets of the data files into the cache of users, while in the delivery phase, the server, upon receiving the specific demands of all users, broadcasts coded packets through the shared link to all users so that each user can extract his desired file from the received packets and the cache content. The main task is to design caching schemes (placement scheme and corresponding delivery scheme) that minimize the rate , which is defined as the maximal transmission amount in the delivery phase among all possible combinations of user demands. The caching scheme in [2] was proven to achieve the optimal rate for uncoded placement [3, 4].
Since the original work of [2], coded caching has attracted significant attention and many works have been done from various aspects of the problem. It was shown in [5] that caching with coded placement can achieve improvement in memoryrate tradeoff in some regime. Caching where files have different popularity scores was studied in [6] and caching where files have differing sizes was studied in [7]. The case of users with heterogenous cache sizes was investigated in [8] and the case of each user demanding multiple files was investigated in [9]. The scenario of decentralized caching was considered in [10], where in the placement phase the cache content of each user is randomly chosen from the file packets. A more general case, hierarchical network with two layers of caches, was considered in [11].
Ia Related Work
Although optimal in rate, the caching scheme in [2] has its limitation in practical implementations: By this caching scheme, each file is divided into packets The number is also referred to as the file size or subpacketization in some literature., which grows exponentially with [12]. For practical application, it is important to construct coded caching scheme with smaller packet number.
So far, several coded caching schemes with reduced file size have been constructed, all with the sacrifice of increasing the rate. In [14], a class of coded caching schemes with linear file size i.e., were constructed from RuzsaSzemredi graphs. A very interesting framework for constructing centralized coded caching scheme, named placement delivery array design (or PDA design for simplicity), was introduced in [15], and some new classes of coded caching schemes were constructed by PDA design in references [15] and [16]. In [17], two classes of constant rate caching schemes with subexponential subpacketization were obtained from free partite hypergraphs. A more general class of coded caching schemes were constructed in [18] from strong edge colored bipartite graphs. References [19] and [20] constructed some coded caching schemes using projective geometries over finite fields, and reference [21] constructed some schemes based on resolvable combinatorial designs from certain linear block codes. Some classes of coded caching schemes from some other block designs, including balanced incomplete block designs (BIBDs), designs and transversal designs (TDs), are obtained in [22]. Summaries of known centralized coded caching schemes can be found in [16, 17] and [19].
IB Our Contributions
In this paper, we first introduce a new perspective of placement delivery array (PDA) design based on binary matrices. It was shown that by this new perspective, the PDA design problem can be simplified. Then, from this new perspective, and based on projective geometries over finite fields and some families of combinatorial designs such as combinatorial configurations and designs, new schemes with low subpacketization for centralized coded caching problem were constructed. We also give a technique for constructing new coded caching scheme from known schemes based on direct product of PDAs.
IC Organization
The rest of this paper are organized as follows. In Section II we introduce the centralized coded caching problem and other related concepts including the placement delivery array (PDA) design and some basic concepts of combinatorial designs. In Section III we give a new perspective of PDA design based on binary matrices. Construction of coded caching schemes based on projective geometries is given in Section IV and constructions based on combinatorial designs are given in Section V. The method of direct product of PDAs is given in Section VI.
Ii Preliminaries
For any positive integer , denote .
For any set , is the size (cardinality) of . If , we call an set; if and , , we call an subset of . Let denote the set of all subsets of and be the power set of .
An array (or vector) is denoted by a bold uppercase letter. If
is an by array, denote . We also use to denote a matrix (array) whose rows are indexed by and columns are indexed by , where and are two sets (not necessarily distinct). For each and , the element of in the th row and the th column is denoted by . We allow that matrices with different subscripts are different, even if the corresponding subscripts denote the identical set. For example, and denote two different matrices even if and are identical set.The following lemma will be used in our discussions.
Lemma 1
[26, Corollary 5.2] If is a regular bipartite graph with , then has a perfect matching.
Iia Centralized Coded Caching Problem
We consider the caching system where one server is connected by users through a shared, errorfree link. The server has a library of files, denoted by , such that each file for some fixed finite field . Moreover, we assume that each user has a local cache memory that can store a vector . We call such system a caching system, or caching system if there is no need to emphasize the cache capacity .^{1}^{1}1The packet number (also known as the file size, or subpacketization) is not a fixed parameter of a caching system. In fact, can vary with different caching schemes. In this work, it is sufficient to assume that is the binary field.
The caching system operates in two phases: the placement phase and the delivery phase. In the placement phase, the vector is computed and allocated into the cache memory of each user . In the delivery phase, each user demands a file , where . The server, informed of the demands of all users, computes a vector for some fixed real number and transmits it to the users, where is called the demand vector. An division coded caching scheme with rate is specified by three sets of functions:

a set of caching functions

a set of encoding functions

a set of decoding functions
such that for all and ,
where and . Such caching scheme is said to have uncoded placement if each coordinate of is a coordinate of some . Otherwise, it is said to have coded placement.
IiB Placement Delivery Array
Placement delivery array (PDA) was introduced in [15] and was shown to be an efficient framework for constructing coded caching schemes. In this subsection, we briefly review the basic idea of the PDA framework.
Definition 1
Let be positive integers such that . An array consisting of symbols from the set is called a placement delivery array (PDA) if the following conditions are satisfied:

The symbol appears exactly times in each column;

Each integer occurs at least once in the array;

For any two distinct pairs , if , then , and .
Lemma 2
[15, Theorem 1] For a given PDA , there exists a corresponding division caching scheme for any caching system with . Precisely, each user is able to decode its requested file correctly for any request d at the rate .
Illustrative examples of PDA and details for constructing caching schemes from PDAs can be found in [15].
IiC Introduction to Combinatorial Designs
We review some basic concepts of combinatorial designs and several families of designs that are related to our constructions of caching schemes. Properties and constructions of such families of designs can be found in [23, 24].
Definition 2 (Design)
A design is a pair , where is a set of elements called points and is a collection (i.e., multiset) of nonempty subsets of called blocks.
A design is said to be simple if it contains no repeated blocks, i.e., is a set (of blocks) rather than a multiset.
Definition 3 (configuration)
A configuration is a design , where is a set of points and is a set of blocks, such that the following conditions are satisfied:

Each block is a subset of ;

Each point is contained in exactly blocks;

Every subset of is contained in at most one block.
It is not hard to verify that condition (iii) is equivalent to the following condition (iii)

Every pair of distinct blocks have at most one point in common.
If is a configuration , we have , or equivalently,
Moreover, since every subset of is contained in at most one block, we have
That is,
from which we can obtain
Equality holds if and only if is a BIBD, which is defined as follows.
Definition 4 (Bibd)
Let and be positive integers such that . A balanced incomplete block design (abbreviated to BIBD) is a design such that the following properties are satisfied:

;

Each block is a subset of ;

Every subset of is contained in exactly one block.
Another important family of designs related to our construction is design.
Definition 5 (design)
Let and be positive integers such that . A design is a design satisfying the following conditions:

;

Each block is a subset of ;

Every subset of is contained in exactly blocks.
A design is also known as a Steiner system and is usually denoted by .
If is a design and such that , then there are exactly
blocks in that contain all points in . In particular, the number of blocks in a design is
Iii A new Perspective of Placement Delivery Array Design
We now show that designing a feasible placement delivery array is equivalent to constructing three binary matrices satisfying some certain conditions.
Theorem 1
There exists a PDA if and only if there exist three binary matrices , and , where is an set, is an set, and is a set, such that the following conditions E1E4 are satisfied:

For every ,

For every ,

For every such that , there is exactly one such that .

For every such that , there is exactly one such that .

For every such that , there is exactly one such that .
proof 1
The proof is given in Appendix A.
The following theorem provides a set of conditions that are sufficient for the existence of a feasible PDA and easier to construct than the conditions in Theorem 1.
Theorem 2
Let , , be three binary matrices, where is an set, is an set, and is a set. For every , denote
and
Then there exists a PDA if the conditions E1E3 and E6 are satisfied, where E1E3 are as in Theorem 1, and

For every and every ,
where
and
proof 2
We will construct a binary matrix such that the matrices , , satisfy conditions E1E5.
Consider the bipartite graph with bipartition and edge set . Clearly, condition E6 implies that is regular, where for any given . By Lemma 1, has a perfect matching . Now, let be a binary matrix such that for each : if for some , and otherwise.
By the construction, it is easy to see that , , satisfy conditions E1E5. Hence, by Theorem 1, there exists a PDA.
The following Corollary can be viewed as a generalization of [13, Theorem 7].
Corollary 1
proof 3
First, as in the proof of Theorem 2, we can construct binary matrices , , satisfying conditions E3E5. Clearly, , , still satisfy conditions E1, E2 and E7, and hence we can easily verify that they satisfy conditions E1E5 of Theorem 1, where . So we can obtain a PDA with , , , and , which proves result (3).
Now, relabelling by , by , and by , we can check that conditions E1E5 of Theorem 1 are still satisfied and we obtain a PDA with , , , and , which proves result (1).
Similarly, relabelling by , and by , we can obtain a PDA with , , , and , which proves result (2).
In the subsequent sections, we will construct binary matrices , and satisfying the desired conditions using various objectives and techniques such as projective geometries over finite fields, combinatorial designs, and the direct product technique. Then, from such matrices, we will construct PDAs and the corresponding caching schemes.
Iv Coded Caching Based on Projective Geometries
As a simple application of Corollary 1, we give a different description of the construction in [19, Theorem 3]. By our method, two more families of PDAs can be obtained.
We first need to introduce the notation of Gaussian binomial coefficient. Let be a prime power. For any nonnegative integers and such that , the Gaussian binomial coefficient (or binomial coefficient), denoted by , is defined as
Clearly, . The following lemma shows some other useful properties of Gaussian binomial coefficient, which can be found in [27].
Lemma 3
Suppose . For any fixed dimensional vector space over , the following hold.

The number of dimensional subspaces of is .

The number of dimensional subspaces of that contain a fixed dimensional subspace of is

The number of dimensional subspaces of intersecting a fixed dimensional subspace of in a fixed dimensional subspace is .
Now, we can give a construction of PDA based on projective geometries over finite fields. Consider positive integers such that . Let be the set of all dimensional subspaces of , be the set of all dimensional subspaces of , and be the set of all dimensional subspaces of . By 1) of Lemma 3, we have , and . We construct three binary matrices , and as follows. For every and :
where 0 is the zero vector of . Moreover, for :
and
Notice the following facts:

Given an dimensional subspace of and a dimensional subspace of such that , there is exactly one dimensional subspace of , i.e., is the direct sum of and , such that and . So Condition E3 is satisfied.

Given an dimensional subspace of and a dimensional subspace of such that , by 3) of Lemma 3, there are dimensional subspaces of such that and . Similarly, given an dimensional subspace of and an dimensional subspace of such that , there are dimensional subspaces of such that and . So condition E6 is satisfied.
By Corollary 1, there exists a PDA such that can be taken as any one of the following values:

;

;

.
By the above three families of PDAs, and by Lemma 2, we can obtain the following theorem.
Theorem 3
Let be positive integers such that . There exists a caching scheme for each of the following three sets of parameters:

, , the rate , and the file size ;

, , the rate , and ;

, , the rate and the file size .
V Coded Caching Based on Combinatorial Designs
In this section, we present some caching schemes constructed from combinatorial designs.
Va Caching Schemes from Configurations
We first give a construction based on combinatorial configurations.
Theorem 4
If there exists a configuration , then there exists a caching scheme for any caching system with each of the following parameter values:

, , and the rate ;

, , , and ;

, , , and .
proof 4
Let be a configuration . Let and . Then and . We construct three binary matrices , and as follows. For every and :
Moreover, for every :
and
It is easy to verify that conditions E1, E2, E3, E6 and E7 are satisfied, where and . By Corollary 1, there exists a PDA, where can be taken as , or .
If , then by Lemma 2, we can obtain a caching scheme with , , and the rate , which proves result (1).
If , then by Lemma 2, we can obtain a caching scheme with , , , and , which proves result (2).
If , then by Lemma 2, we can obtain a caching scheme with , , , and , which proves result (3).
We can also compare our construction with the optimal caching scheme in [2]. Consider the result (1) of Theorem 4. We have and . Note that in a configuration,
Then we have
Equality holds if and only if the corresponding configuration is a BIBD. Now, suppose there exists a BIBD, then by (1) of Theorem 4, we can construct a caching scheme with and, for fixed and large , we have
Note that the optimal rate is achieved using an exponentially growing subpacketization . In comparison, our construction uses linear subpacketization and the rate satisfies
In summary, our construction uses a linear subpacketization and achieves the rate that differs from the optimal rate by a factor of .
VB Caching Schemes from  Designs
In this subsection, we present two constructions of caching schemes from  designs. The first construction comes from  designs with (see Theorem 5) and the second construction comes from  designs with (see Theorem 7).
Theorem 5
Suppose there exists a  design with . Let be a positive integer such that . Then there exists a caching scheme for any caching system with each of the following parameter values:

, , and ;

, , the rate , and the file size ;

, , , and .
proof 5
Let be a design with . Let and . Then and . We construct three binary matrices , and as follows. For every and :
Moreover, for every :
and
It is easy to verify that conditions E1, E2, E3, E6 and E7 are satisfied, where
Comments
There are no comments yet.