A survey of the study of combinatorial batch code

Abstract

A combinatorial batch code has strong practical motivation in the distributed storage and retrieval of data in a database. In this survey, we give a brief introduction to the combinatorial batch codes and some progress.

Keywords

Combinatorial batch codes / optimal CBC / uniform CBC / set system

1 Introduction

In 2004, Ishai et al. first proposed the concept of batch codes based on the actual background of data storage in [12]. Assuming that there is a large database containing n item data, it is now necessary to allocate this n item data to m servers (different servers can have the same data, and this process can be regarded as encoding). After the data is allocated, when any k item data in the n item data is needed, it is hoped that each server can read up to t item (for load balancing between servers) to recover this k item data (this process can be regarded as decoding). The concept of batch code is obtained by abstracting the above problems: the \left(n,N,k,m,t\right) batch code on character set \mathrm{\Sigma } encodes the string x\in {\mathrm{\Sigma }}^n into m group string y_1,y_2,\dots ,y_m\in {\mathrm{\Sigma }}^{\ast } (also known as server), and the total length of this m group string is N, so that for k different index metrics i_1,i_2,\dots ,i_k\in \left\{1,2,\dots ,n\right\}, the information at each of the k positions corresponding to x_{i_1},x_{i_2},\dots ,x_{i_k} in x can be translated by reading up to t messages from each server. In [12], Ishai et al. introduced some important applications of batch code and their connection with practical problems, described the relationship between this type of code and other types, and gave several methods to construct batch code. Among the many encoding and decoding modes of batch code, Ishai et al. gave the simplest coding and decoding mode, that is, it does not need to be encoded when stored, but is stored directly, so the decoding is to read out directly. They call it a replication-based batch code. Because the structure of this batch code has pure combination characteristics, in 2009, Paterson et al. called it combinatorial batch codes in [15], referred to as CBC for short. Since then, people have begun to study CBC from the perspective of pure combination. Here, the finely determined fork of CBC is transcribed as follows.

Definition 1.1 [15]　An \left(n,N,k,m,t\right)-CBC is a set system \left(X,\mathcal{B}\right), where X is a set of n elements, \mathcal{B} is a collection of m subsets of X and N=\sum _{B\in \mathcal{B}}|B|. For each k-subset \left\{x_{i_1},x_{i_2},\dots ,x_{i_k}\right\}\subseteq X, there exists a subset C_i\subseteq B_i, where \left|C_i\right|⩽t,i=1,2,\dots ,m, such that

\left\{x_{i_1},x_{i_2},\dots ,x_{i_k}\right\}=\bigcup _{i=1}^m{C}_i,

where the elements of X are called points and the elements of \mathcal{B} are called intervals.

For the given parameter n,k,m,t, the desired CBC should minimize the total storage amount in each server (i.e., the value of N), in order to save as much storage space as possible. CBC that meets this condition is called optimal, and this optimal value is denoted as N_t\left(n,k,m\right). Therefore, finding this optimal value is the key to constructing the optimal CBC. Up to now, most of the research results are aimed at the situation of t=1. Obviously, when t=1, it is required to read up to 1 element from each server. At this time, CBC is synxed as \left(n,N,k,m\right)-CBC, and the optimal value is s synxed as N\left(n,k,m\right).

In addition to the above analysis and construction of the combinatorial batch codes from the perspective of saving storage space, we can also consider the optimality of the combinatorial batch codes from another perspective, that is, the so-called storage rate \frac{n}{N}. The existing conclusions have shown that for fixed k,m, when n\to \mathrm{\infty }, the optimal storage rate of \left(n,N,k,m\right)-CBC is close to \frac{1}{k}. Therefore, the following questions become very meaningful: for fixed \frac{n}{N} and k, how to construct \left(n,N,k,m\right)-CBC with the largest n (at this time, n is a function of m). Paterson et al. proposed a special type of CBC in [15], that is, each element of it is stored in c servers, that is to say, the storage rate is \frac{1}{c}. Such CBC is called c consistent. The study of the optimal properties of this kind of CBC is the given parameter m,c,k,t, find the maximum value of n that is consistent \left(n,cn,k,m,t\right)-CBC. This maximum value is recorded as n_t\left(m,c,k\right), and when t=1, it is written as n\left(m,c,k\right). Consistent CBC reaching this maximum value is called optimal.

In addition, Chen introduced a combinatorial batch codes called ECBC codes in his master’s thesis [11], that is, each the combinatorial batch codes with the same number of elements in the server, and some preliminary research results have been obtained.

In the past three years, we have conducted a preliminary study on the combinatorial batch codes. In this process, we have collected almost all the literature about the combinatorial batch codes so far, and wrote this article on the basis of careful study. For CBC and uniform CBC, we have some major research results are introduced and summarized, hoping to be helpful for subsequent research.

2 Determine the condition for the set system to become the combinatorial batch codes

Generally speaking, it is difficult to directly judge whether a set system meets the conditions of the combinatorial batch codes according to the definition. Therefore, people need to start from the definition and find some conditions to indirectly determine whether a set system is a combinatorial batch code with certain parameters. The research results in this regard mainly focus on two aspects: first, the association matrix of the set system (group mark row, point mark column); second, the dual set system.

Paterson et al. [15] gave a judgment that the \left(0,1\right) matrix is the sufficient and necessary condition of the CBC's association marix: an m\times n\left(0,1\right) matrix \Gamma is the association matrix of \left(n,N,k,m\right)-CBC if and only if for any k column of \Gamma, it contains a k\times k submatrix, and there is at least one transversal containing k ones at this submatrix.

The dual set system (Y,\mathcal{F}) of (n,N,k,m)-CBC is denoted as {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }(n,N,k,m), where |Y|=m,|\mathcal{F}|=n,\sum _{F\in \mathcal{F}}|F|=N. Buitas et al. [7] presented 4 equivalent conditions for determing whether a set system is {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }(n,N,k,m), i.e., becoming a (n,N,k,m)-CBC dual set system.

(1) \left(Y,\mathcal{F}\right) is a {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(k\right) system, that is, for every l\left(1⩽l⩽k\right) element subsystem {\mathcal{F}}^{{}^{\prime }}=\left\{F_1,F_2,\dots ,F_l\right\}\subseteq \mathcal{F}, there exist l of Y mutually different elements y_1,y_2,\dots ,y_l, such that y_i\in F_i holds for every 1⩽i⩽l.

(2) \left(Y,\mathcal{F}\right) satisfies the k-Hall condition, that is, every subsystem {\mathcal{F}}^{{}^{\prime }} of i\left(1⩽i⩽k\right) members of \mathcal{F} satisfies the inequality \left|\bigcup _{F\in {\mathcal{F}}^{{}^{\prime }}}F\right|⩾i.

(3) For any 1⩽j⩽k-1, every j element subset of Y contains at most j groups from the system \mathcal{F}.

(4) For any 1⩽j⩽k-1, every m-j element subset of Y intersects at least n-j groups from the system \mathcal{F}.

The later research shows that the above conclusion has become a powerful tool to verify whether a set system is CBC.

For general t, Buitas et al. [8] gave a similar conclusion.

For positive integers k,t, if each subset {\mathcal{F}}^{{}^{\prime }}=\left\{F_1,F_2,\dots ,F_l\right\}\subseteq \mathcal{F},1⩽l⩽k, there are elements y_1,y_2,\dots ,y_l such that y_i\in F_i holds for every 1⩽i⩽l, and the multiple of each element of Y in y_1,y_2,\dots ,y_l is at most t, then the set system \left(Y,\mathcal{F}\right) is a {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(k,t\right) system. If for each subset {\mathcal{F}}^{{}^{\prime }}\subseteq \mathcal{F},\left|{\mathcal{F}}^{{}^{\prime }}\right|⩽k, satisfying \left|\bigcup _{F\in {\mathcal{F}}^{{}^{\prime }}}F\right|⩾\frac{\left|{\mathcal{F}}^{{}^{\prime }}\right|}{t},it is said that the set system \left(Y,\mathcal{F}\right) meets the (k,t)-Hall condition. Therefore, the following three equivalent conditions can be used to determine that the set system \left(Y,\mathcal{F}\right) is a dual set system of \left(n,N,k,m,t\right)-CBC.

(1) \left(Y,\mathcal{F}\right) is a {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(k,t\right)-system.

(2) \left(Y,\mathcal{F}\right) satisfies the \left(k,t\right)-Hall condition.

(3) For any , every l element subset of Y contains at most lt members of \mathcal{F}.

3 The construction and optimal value of the combinatorial batch codes

For any given parameter several n,k,m, the problem of determining N(n,k,m) has not been completely solved. So, in some cases, it is impossible to judge whether the constructed CBC is optimal. There are roughly two ways to determine N(n,k,m). Fisrt, the constructed CBC determines the upper bound of N(n,k,m), and then determines that the upper bound is also the lower bound of N(n,k,m) through further discussion, so that the optimal CBC construction of the given parameter is solved together with the optimal value problem. Second, directly determine by discussing the combinatorial properties of the CBC with given parameters.

In 2009, Paterson et al. [15] first conducted a detailed study on the combinatorial batch codes when t=1. For parameters n,k,m, Paterson et al. gave the optimal value of CBC in a variety of cases.

(1) Two ordinary situations.

When m=n, n different points are stored separately in n servers to get (n,n,k,n)-CBC. Obviously, it is optimal. When m=k, the optional k points are stored in the k servers, respectively, and the remaining n-k points are stored once in each server, which means \left(n,k\left(n-k+1\right),k,k\right)-CBC, this CBC is also optimal. If , then at least one server contains n-k or fewer points. For k points in this server, they cannot be read as required, see the following theorem.

Theorem 3.1 [15]　 N\left(n,k,n\right)=n,N\left(n,k,k\right)=kn-k\left(k-1\right).

(2) The situation when n=m+1.

Paterson et al. [15] used the (k,p)-FS diagram to construct the association matrix of CBC to get a \left(m+p,m+p+ϵ\left(k,p\right),k,m\right)-CBC, of which,

\nu (k,p)=\frac{(p+2)(k-2)}{3}+2,\epsilon (k,p)=\frac{p(k+1)}{3}+\frac{2(k-2)}{3},

where k,p is a positive integer, k\equiv 2(\mathrm{m}\mathrm{o}\mathrm{d}3),m⩾\nu \left(k,p\right). When k\equiv 0\left(\mathrm{m}\mathrm{o}\mathrm{d}3\right) or k\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}3\right), there is a similar structure respectively. In this way, the upper bound of N(m+p,k,m) is determined, and then they prove that the upper bound is also at the lower bound of N(m+p,k,m) at p=1, so there is

Theorem 3.2 [15]　 N\left(m+1,k,m\right)=m+k.

You can see that the n values in this optimal construction are only 1 more than the m value. When k,p take other values, CBC constructed by this method is not sure if it is optimal. For the so-called “large” n, Paterson et al. also studied in [15].

(3) The situation when n⩾(k-1)\left(\begin{array}{c}m\\ k-1\end{array}\right).

For the case of n⩾(k-1)\left(\begin{array}{c}m\\ k-1\end{array}\right), Paterson et al. construct the group in the dual set system of CBC as all k-1 subsets of m element set repeat k-1 times, and the others are arbitrary k element subsets. By k-Hall condition that each k-1 element subset can be repeated at most k-1 time, so that a {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(n,kn-(k-1)\left(\begin{array}{c}m\\ k-1\end{array}\right),k,m\right). To prove this CBC is optimal, they constructed a \left(\begin{array}{c}m\\ k-1\end{array}\right)\times n association matrix. By calculating the number of 1 in association matrix, it is concluded that when the number of long groups in CBC's dual set system i\left(i=1,2,\dots ,k-2\right) is 0, N\left(n,k,m\right) has a minimum lower bound, and this lower bound is exactly kn-\left(k-1\right)\left(\begin{array}{c}m\\ k-1\end{array}\right). This also shows that the constructed CBC is optimal.

Theorem 3.3 [15]　 If n⩾\left(k-1\right)\left(\begin{array}{c}m\\ k-1\end{array}\right), then N\left(n,k,m\right)=kn-\left(k-1\right) \left(\begin{array}{c}m\\ k-1\end{array}\right).

Subsequently, people studied the situation when n⩽\left(k-1\right)\left(\begin{array}{c}m\\ k-1\end{array}\right). For the “slightly smaller” n. When \left(\begin{array}{c}m\\ k-2\end{array}\right)⩽n⩽\left(k-1\right)\left(\begin{array}{c}m\\ k-1\end{array}\right), Ruj et al. [16] and Bhattacharya et al. [2] according to the optimal {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left((k-1)\left(\begin{array}{c}m\\ k-1\end{array}\right),N,k,m\right), the optimal CBC for this “slightly smaller” n is constructed in different ways. Bujitas et al. [6] get the optimal value of CBC by direct calculation.

Theorem 3.4 [2, 6, 16]　 If m⩾k⩾3,\left(\begin{array}{c}m\\ k-2\end{array}\right)⩽n⩽\left(k-1\right)\left(\begin{array}{c}m\\ k-1\end{array}\right), then

N(n,k,m)=(k-1)n-\lfloor \frac{(k-1)\left(\begin{array}{c}m\\ k-1\end{array}\right)-n}{m-k+1}\rfloor .

So far, when n⩾\left(\begin{array}{c}m\\ k-2\end{array}\right), the optimal value and optimal construction problems of CBC have been completely solved. Next, we need to study the optimal value and optimal structure of CBC when . This process doesn't seem to be going well.

In 2012, Bhattacharya et al. [2] gave an incomplete conclusion. On the basis of the construction of the optimal {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(\left(\begin{array}{c}m\\ k-2\end{array}\right),N,k,m\right), they use binary constant recoding to construct the \left(n,N,k,m\right)-CBC when \left(\begin{array}{c}m\\ k-2\end{array}\right)-(m-k+1)A(m,4,k-3)⩽n⩽\left(\begin{array}{c}m\\ k-2\end{array}\right) (A(m,4,k-3) is the maximum number of code words of binary constant code with a length of m, weight of k-3, and Hamming distance of 4), of which N=n(k-2)-2\lfloor \frac{\left(\begin{array}{c}m\\ k-2\end{array}\right)-n}{m-k+1}\rfloor. It also proves that only part of this structure is the optimal CBC, the other part of the CBC can't determine the optimality, but only knows one of their upper bounds.

Theorem 3.5 [2]　 Let \left(\begin{array}{c}m\\ k-2\end{array}\right)-(m-k+1)A(m,4,k-3)⩽n⩽\left(\begin{array}{c}m\\ k-2\end{array}\right),

then when ,

N(n,k,m)=n(k-2)-\lfloor \frac{2\left(\left(\begin{array}{c}m\\ k-2\end{array}\right)-n\right)}{m-k+1}\rfloor ;

when ,

N(n,k,m)⩽n\left(k-2\right)-2\lfloor \frac{\left(\begin{array}{c}m\\ k-2\end{array}\right)-n}{m-k+1}\rfloor .

For smaller n values, it is difficult to determine the optimal value of CBC in batches. Brualdi et al. proved the Theorem 3.2 with a new method in [3, 4], and connected CBC with the transverse matrix along this road, using the transverse matrix to obtain the optimal structure of CBC when n=m+2. In [7], Buitas et al. use the pure combination method to discuss the CBC in detail after the nature of the dual set system, the optimal value of CBC when n=m+2 is obtained, and a construction method is given.

Theorem 3.6 [3, 7]　 When k⩽m⩽k+\sqrt{k},

N(m+2,k,m)=2m+\lfloor \frac{k}{m-k+1}\rfloor ;

when m>k+\sqrt{k},

N(m+2,k,m)=m+k-2+\lfloor 2\sqrt{k+1}\rfloor .

Naturally, according to this idea, the situation should be discussed when n=m+3, but this discussion is more complicated. Chen et al. [10], Jia et al. [13] only gave the optimal value in the case of k=4 and k=5,6, respectively.

Theorem 3.7 [10]　 For m⩾5, there are

N(m+3,4,m)=\{\begin{array}{ll}15,& m=5;\\ m+9,& m⩾6.\end{array}

Theorem 3.8 [13]　(1) For m⩾6, there are

N(m+3,5,m)=\{\begin{array}{ll}18,& m=6;\\ m+11,& m⩾7.\end{array}

(2) For m⩾7, there are

N(m+3,6,m)=\{\begin{array}{ll}21,& m=7;\\ m+13,& m⩾8.\end{array}

The above two results mainly benefit from the quantitative relationship between m and n (here n=m+3), the k-Hall conditions that need to be met in CBC's dual set system when k take smaller values (the method in [13] is not applicable to larger k) and the so-called monotonous nature of CBC' optimal value.

Theorem 3.9 [7]　 N(n+1,k,m+1)⩽N(n,k,m)+1.

Theorem 3.10 [10]　 For ,

\begin{array}{rl}& N(n,k,m+1)⩽N(n,k,m)-1,\\ & N(n+1,k,m)⩾N(n,k,m)+2,\\ & N(n,k+1,m)⩾N(n,k,m).\end{array}

In addition to discussing the optimal CBC along the path of n=m+q,q=1,2,3,\dots, Bujtas et al. gave another path.

For k=1, N(n,1,m)=n is ordinary. For k=2, N(n,2,m)=2n-m can be obtained from Theorem 3.3. For k=3, according to Theorem 3.3 and Theorem 3.4, it can be concluded that when n⩽m^2-m, N(n,3,m)=2n-m+\lfloor \frac{n-3}{m-2}\rfloor. when n⩾m^2-m, N(n,3,m)=3n-m^2+m. Therefore, it seems feasible to study along k=4,5,6,\dots. However, the optimal value of CBC is much more complicated when k=4. In [6], Bujtás et al. analyzed the type of CBC* (k) system (called the type of the set system \left(Y,\mathcal{F}\right) is \left[a,b\right], if there is a⩽\left|F\right|⩽b for each F\in \mathcal{F}, the following conclusion is reached.

Lemma 3.1 [6]　 If k⩾3, there is an optimal {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(n,N,k,m\right), \left(Y,{\mathcal{F}}^{{}^{\prime }}\right) for each optimal {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(n,N,k,m\right), \left(Y,\mathcal{F}\right), its type is \left[1,k-1\right] or \left[k-1,k\right].

In particular, when k=4, Bujtás et al. [6] made some changes to the structure of {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(n,N^{{}^{\prime }},4,m\right),\left(Y,{\mathcal{F}}^{{}^{\prime }}\right), so that the number of singletons, pairs and triplets group of {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(n,N^{{}^{\prime }},4,m\right), \left(Y,{\mathcal{F}}^{{}^{\prime }}\right) is the same as \mathcal{F}, respectively, and there is no pairs group in {\mathcal{F}}^{{}^{\prime }}. The elements in each singletons set belong to a pairs group at most, which simplifies the structure of {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(n,N^{{}^{\prime }},4,m\right), and does not change the size of the total storage amount of N^{{}^{\prime }}. Similarly, we can require the optimal {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(n,N,4,m\right) to have such a structure. Bujtás et al. proved that if there is a optimal {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(n,N,4,m\right) with type [1,3], then there is an optimal {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(n,N,4,m\right) with type [1,2] or [2,3].

Lemma 3.2 [6]　 For every integers m,n, n⩾m⩾4, there exists an optimal {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(n,N,4,m\right) of type [1,2], [2,3]or[3,4].

Obviously, when , it can be seen from the 4-Hall condition that any n different two element subsets can be used as a group to get a {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(n,N^{{}^{\prime }},4,m\right). Therefore, when , N\left(n,4,m\right)⩽2n. According to Lemma 3.2, there is an optimal {\mathrm{C}\mathrm{B}\mathrm{C}}^{\ast }\left(n,N,4,m\right) of type [1,2]. At this time, it is only necessary to determine the maximum number of single point sets in the dual set system under the condition of 4-Hall.

Theorem 3.11 [6]　 For every integers m,n, n⩾m⩾4,

(a) N(n,4,m)=n, if n=m;

(b) N(n,4,m)=2n-m+\lceil \frac{1+\sqrt{8n-8m+1}}{2}\rceil, if and m is even, or if and m is odd;

(c) N(n,4,m)=2n-m+\lceil \frac{5+\sqrt{8n-16m+25}}{2}\rceil, if and m is even, or if and m is odd;

(d) N(n,4,m)=2n-\frac{m-1}{2}, if n=\frac{m^2+4m+11}{8} (m is odd);

(e) N(n,4,m)=3n-\lfloor \frac{m^2}{2}-\frac{n-m}{m-3}\rfloor, if ;

(f) N(n,4,m)=4n-3\left(\begin{array}{c}m\\ 3\end{array}\right), if 3\left(\begin{array}{c}m\\ 3\end{array}\right)⩽n.

The method of calculating N(n,4,m) by Bujtás et al. is very unique, and the 4-Hall condition is relatively simple. Calculate N(n,5,m) in this way obviously doesn't work, because the 5-Hall condition is more complicated than the 4-Hall condition, so you need to get the optimal value of CBC when k=5 also requires a new calculation method applicable to 5-Hall conditions.

In addition to some “batch” CBC optimal values identified above, there are also some sporadic results.

Bhattacharya et al. [2] gave a lower bound of the CBC optimal value when 1⩽n⩽\left(k-1\right)\left(\begin{array}{c}m\\ k-1\end{array}\right).

Theorem 3.12 [2]　 Let 1⩽n⩽\left(k-1\right)\left(\begin{array}{c}m\\ k-1\end{array}\right),1⩽c⩽k-1, c is the smallest integer that meets the following conditions,

n⩽\frac{(k-1)\left(\begin{array}{c}m\\ c\end{array}\right)}{\left(\begin{array}{c}k-1\\ c\end{array}\right)}.

Then there is

(1)\begin{array}{l}N(n,k,m)⩾nc-\lfloor {\displaystyle \frac{(k-c)\left(\frac{(k-1)\left(\begin{array}{c}m\\ c\end{array}\right)}{\left(\begin{array}{c}k-1\\ c\end{array}\right)}-n\right)}{m-k+1}}\rfloor .\end{array}

It can be seen that the optimal value in Theorem 3.4 and Theorem 3.5 is equal to the lower bound in (1), and the value at the right end of the inequality in Theorem 3.5 is only different from the lower bound in (1). Silberstein et al. in [17] (q^2+q-1,q^3-q,q^2-q-1,q^2-q)-\mathrm{C}\mathrm{B}\mathrm{C} are constructed by decomposable cross-sectional design \mathrm{R}\mathrm{T}\mathrm{D}(q-1,q) (q⩾3 is the prime powers). They used the above theorem to calculate in CBC, N=q^3-q is equal to the lower bound with (1), so there is N\left(q^2+q-1,q^3-q,q^2-q-1,q^2-q\right)=q^3-q. Some people once guessed that the lower bound in (1) was a infimum, but there have been counterexamples to show that the lower bound is not the exact bound. Liu Xian et al. constructed a category (q^2+q-2,q^3-q^2-2q,q^2-2q-3,q^2-2q)-\mathrm{C}\mathrm{B}\mathrm{C} through \mathrm{R}\mathrm{T}\mathrm{D}(q-2,q) in [14], but its optimality cannot be judged by the above theorem.

Up to a few days ago, almost all people's sunlight was focused on the situation of t=1. For t⩾2, only Rui et al. [16] and Buitás et al. [5, 8] gave some conclusions about the optimal value of CBC.

Theorem 3.13 [16]　 N_t(n,k,n)=n; if n⩽tk, then N_t(n,k,k)=n.

Theorem 3.14 [5, 8]　 If m⩾\lceil \frac{k}{t}\rceil ⩾3, n⩾t\left(\lceil \frac{k}{t}\rceil -1\right)\left(\begin{array}{c}m\\ \lceil \frac{k}{t}\rceil -1\end{array}\right), then

N_t(n,k,m)=n\lceil \frac{k}{t}\rceil -t\left(\lceil \frac{k}{t}\rceil -1\right)\left(\begin{array}{c}m\\ \lceil \frac{k}{t}\rceil -1\end{array}\right).

If m⩾\lceil \frac{k}{t}\rceil ⩾3,t\left(\begin{array}{c}m\\ \lceil \frac{k}{t}\rceil -2\end{array}\right)⩽n⩽t\left(\lceil \frac{k}{t}\rceil -1\right)\left(\begin{array}{c}m\\ \lceil \frac{k}{t}\rceil -1\end{array}\right), then

N_t(n,k,m)=n\left(\lceil \frac{k}{t}\rceil -1\right)-\lfloor \frac{t\left(\lceil \frac{k}{t}\rceil -1\right)\left(\begin{array}{c}m\\ \lceil \frac{k}{t}\rceil -1\end{array}\right)-n}{m-\lceil \frac{k}{t}\rceil +1}\rfloor .

If k⩽t, all points can be stored in one server. Therefore, if \lceil \frac{k}{t}\rceil =1, then N_t(n,k,m)=n. For \lceil \frac{k}{t}\rceil to take other values, Bujtás et al. came to the following conclusion.

Theorem 3.15 [5, 8]　 If \lceil \frac{k}{t}\rceil =2, m⩾2, then

(a) if n⩽tm, then N_t(n,k,m)=n;

(b) if n>tm, then N_t(n,k,m)=2n-tm.

Theorem 3.16 [5, 8]　 If \lceil \frac{k}{t}\rceil =3, m⩾3, then

(a) If n⩽tm, then N_t(n,k,m)=n;

(b) If , then N_t(n,k,m)=2n-\lceil \frac{m\left(m-1\right)t-n}{m-2}\rceil;

(c) If , then N_t(n,k,m)=3n-tm\left(m-1\right).

4 Uniform combinatorial batch codes

There are not many precise conclusions about the optimal value n(m,c,k) that needs to be determined in the uniform combination batch code, and the optimal uniform combination batch code as a general (n(m,c,k),cn,k,m)-CBC needs to be further studied. Paterson et al. gave an upper bound of n(m,c,k) in [15].

Theorem 4.1 [15]

(2)n(m,c,k)⩽\frac{(k-1)\left(\begin{array}{c}m\\ c\end{array}\right)}{\left(\begin{array}{c}k-1\\ c\end{array}\right)}.

Paterson et al. [15] constructed some uniform CBC, particularly the points stored (i.e., the value of n) is equal to the upper bound of c=k-1 and c=k-2 of Theorem 4.1 when uniform \left(c\left(\begin{array}{c}m\\ c\end{array}\right),c^2\left(\begin{array}{c}m\\ c\end{array}\right),c+1,m\right)-\mathrm{C}\mathrm{B}\mathrm{C} of c=k-1 and \left(\left(\begin{array}{c}m\\ c\end{array}\right),c\left(\begin{array}{c}m\\ c\end{array}\right),c+2,m\right)-\mathrm{C}\mathrm{B}\mathrm{C} of c=k-2. That is to say, these two uniform CBC is optimal.

Theorem 4.2 [15]　 n(m,c,c+1)=c\left(\begin{array}{c}m\\ c\end{array}\right),n(m,c,c+2)=\left(\begin{array}{c}m\\ c\end{array}\right).

From the above conclusion, it can be seen that when c=1,k-1,k-2, the upper bound in (2) is the supremum. When 2⩽c⩽k-3, the upper bound of n(m,c,k) can only be obtained by Theorem 4.1 is O\left(m^c\right). In 2014, Balachadran and Bhattacharya improved the upper bound of (2) in [1], and it is concluded that if 3⩽c⩽k-1-\lceil \log k\rceil, then there is n(m,c,k)=O\left(m^{c-\frac{1}{2^{c-1}}}\right). After that, Bujtás et al. [9] further improved and found a better upper bound when c⩽\frac{k}{2}-1, that is, n(m,c,k)=O\left(m^{c-1+\frac{1}{\lfloor \frac{k}{c+1}\rfloor }}\right).

Paterson et al. [15] used the probability method to discuss a lower bound of n(m,c,k): for the definite integer k,c(k⩾2,c⩾2), there is a uniform (n,cn,k,m)-CBC and n⩾a_{c,k}{m}^{\frac{ck}{k-1}-1}, where a_{c,k} is the normal number that only depends on c,k, that is to say, n(m,c,k)=\mathrm{\Omega }\left(m^{\frac{ck}{k-1}-1}\right). Balachandran et al. [1] have reached this conclusion that the lower bound of the c=2 (i.e., \mathrm{\Omega }\left(m^{\frac{k+1}{k-1}}\right)) has been improved, and the following theorem is obtained.

Theorem 4.3 [1]　 Set k⩾8, then

n(m,2,k)=\{\begin{array}{ll}\mathrm{\Omega }\left(m^{\frac{k-3}{k-5}}\right),& k\equiv 5(\mathrm{m}\mathrm{o}\mathrm{d}6);\\ \mathrm{\Omega }\left(m^{\frac{k-2}{k-4}}\right),& k\equiv 2(\mathrm{m}\mathrm{o}\mathrm{d}6)\text{or}k\equiv 4(\mathrm{m}\mathrm{o}\mathrm{d}6);\\ \mathrm{\Omega }\left(m^{\frac{k-1}{k-3}}\right),& k\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}6)\text{or}k\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}6);\\ \mathrm{\Omega }\left(m^{\frac{k}{k-2}}\right),& k\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}6).\end{array}

At the same time, Ballachandran et al. [1] have also improved the upper bound of n(m,2,k).

Theorem 4.4 [1]

n(m,2,k)=\{\begin{array}{ll}O\left(m^{1+\frac{1}{\lfloor k/4\rfloor }}\right),& k⩾4,\\ \mathrm{\Theta }\left(m^{\frac{3}{2}}\right),& k=6,7,8.\end{array}

When c=2, the exact values of n(m,2,3) and n(m,2,4) can be obtained from Theorem 4.2. In addition, Balachadran et al. the exact value of k=5 is given.

Theorem 4.5 [1]　 n(m,2,5)=\lfloor \frac{m^2}{4}\rfloor ,m⩾5.

Silberstein et al. [17] constructed the uniform \left(q^2+q,q^3+q^2,q^2,q^2\right)-CBC (q is the prime powers), and constructed by a decomposable transverse design \left(q^2-3,(q-1)\left(q^2-3\right),q^2-q-1,q^2-q-1\right)-CBC, from the upper bound of (2), it can be seen that these two uniform CBC are optimal. Silberstein et al. [17] constructed uniform (h^2,2h^2,5,2h)-CBC and uniform (h^2-h,2\left(h^2-h\right),5,2h-1)-CBC according to the transverse design TD(2,h). From the conclusion in Theorem 4.5, it can be seen that these two uniform CBC is optimal. When , Bhattacharya et al. constructed (n,cn,k,m)-CBC by the original constant code in [2], where n=|\mathcal{F}|=(k-c-1)A(m,2(k-c-1),c).

When t⩾2, there are few studies on the optimal value n_t(m,c,k) of the uniform CBC, and only Ruj et al. gave in [16] some of the following conclusions.

Theorem 4.6 [16]　 If k⩽2t, then n_t(m,2,k)=\mathrm{\infty }.

Theorem 4.7 [16]　(a) n_t(m,c,ct+i)=ct\left(\begin{array}{c}m\\ c\end{array}\right),i⩽t;

(b) n_t(m,c,ct+t+j)=t\left(\begin{array}{c}m\\ c\end{array}\right),j⩽t;

(c) If k>tm, then .

Theorem 4.8 [16]　(a) n_2(m,2,9)⩾\left(\begin{array}{c}m\\ 2\end{array}\right)+2\lfloor \frac{m}{3}\rfloor;

(b) n_2(m,2,10)⩾\left(\begin{array}{c}m\\ 2\end{array}\right)+2+3\lfloor \frac{m-3}{2}\rfloor.

References

[1] Balachandran N, Bhattacharya S. On an extremal hypergraph problem related to combinatorial batch codes. Discrete Appl Math 2014; 162: 373–380

[2] Bhattacharya S, Ruj S, Roy B. Combinatorial batch codes: a lower bound and optimal constructions. Adv Math Comm 2012; 6(2): 165–174

[3] Brualdi R A, Kiernan K P, Meyer S A, Schroeder M W. Combinatorial batch codes and transversal matroids. Adv Math Comm 2010; 4: 419–431

[4] Brualdi R A, Kiernan K P, Meyer S A, Schroeder M W. Erratum to “Combinatorial batch codes and transversal matroids”. Adv In Math Comm 2010; 4(3): 597

[5] Bujtás C, Tuza Z. Combinatorial batch codes: extremal problems under Hall-type conditions. Electron Notes Discrete Math 2011; 38: 201–206

[6] Bujtás C, Tuza Z. Optimal batch codes: many items or low retrieval requirement. Adv Math Comm 2011; 5(3): 529–541

[7] Bujtás C, Tuza Z. Optimal combinatorial batch codes derived from dual systems. Miskolc Math Notes 2011; 12(1): 11–23

[8] Bujtás C, Tuza Z. Relaxations of Hall’s condition: optimal batch codes with multiple queries. Appl Anal Discrete Math 2012; 6(1): 72–81

[9] Bujtás C, Tuza Z. Turán numbers and batch codes. Discrete Appl Math 2015; 186: 45–55

[10] Chen J F, Zhang S M, Zhang G S. Optimal combinatorial batch code: monotonicity, lower and upper bounds. Sci Sin Math 2015; 45(3): 311–320

[11] ChenS B. A New Combinatorial Batch Code. Master Thesis. Beijing: Beijing Jiaotong University, 2010 (in Chinese)

[12] IshaiYKushilevitzEOstrovskyRSahaiA. Batch codes and their applications, In: STOC’04 (Proceedings of the 36th Annual ACM Symposium on Theory of Computing). New York, 2004, 262–271

[13] Jia D D, Zhang G S, Yuan L D. A class of optimal combinatorial batch code. Acta Math Sin, Chin Ser 2016; 59(2): 267–278

[14] Liu X, Zhang S M, Zhang G S. Combinatorial batch codes based on RTD (q−2, q). Adv Math (China) 2016; 45(5): 700–710

[15] Patterson M B, Stinson D R, Wei R. Combinatorial batch codes. Adv Math Comm 2009; 3(1): 13–27

[16] RujSRoyB. More on combinatorial batch codes. arXiv: 0809.3357v1

[17] Silberstein N, Gál A. Optimal combinatorial batch codes based on block designs. Des Codes and Cryptogr 2016; 78: 409–424

RIGHTS & PERMISSIONS

Higher Education Press 2023