Research On Some Combinatorial Batch Codes

Batch codes, first introduced by Ishai, Kushilevitz, Ostrovsky and Sahai in2004, are methods for solving the data storage problem. The actual background is how to distribute a database of n items among m servers in such a way that when a user needs any k of the n items, he can read at most t items from each server to find them and meanwhile the total storage N is required to be as small as possible. If we restrict out attention to batch codes in which every server stores a subset of the n items, we will get an (n,N,k,m,t) Combinatorial Batch Code (hereinafter referred to as CBC). In the practical application, only the case t=1is considered. Given n, k and m, we would like to find the (n, N, k, m)-CBC for which the total storage is minimum among all (n, N’, k, m)-CBCs. Here we say it is optimal and we denote the corresponding value of N by N(n,k,m). When using CBC to solve practical problems, the value of N is required to be as small as possible for given parameters n, k and m.The main content in this thesis is to research the monotonicity properties of the optimal CBC and determine the value of N in a class of optimal CBC. In2008, Paterson and Stinson gave the value of N(m+1,k,m) while Richard and Kathleen gave the value of N(m+2, k, m), then we try to determine the value of N(m+3, k, m) with the continuation of the ideology above. When k=1, obviously, N(m+3,1,m)=m+3. Meanwhile, the values of N(m+3,2,m) and N(m+3,3,m) were both determined by Paterson and Ruj, et al. In addition, they also determined the value of N(m+3, k,m) whenm+3≥(k-1)(mk-1)and(mk-2)≤m+3≤(mk-1), but the value of N(m+3, k,m) has not yet been determined when m+3<(mk-2).It is more difficult to determine the value of N(m+3,k,m) for the general case. In this paper, we mainly study the special case k=4, that is to say, we will determine the value of N(m+3,4,m).The structure of this thesis is as follows:In the first chapter, we present some monotonicity properties of the optimal CBC and prove that when N(n1, k,m1)=t1and N(n2,k,m2)=t2, the(n1+n2,t1+t2, k,m1+m2)-CBC exits.In the second chapter, firstly, we come to a conclusion that N(9,4,6)=15using dual theorem, then we obtain N(m+3,4,m)=m+9(m>6) through the combination of monotonicity properties of the optimal CBC and the use of the recursive inequality.In the third chapter, we conclude that N(8,4,5)=15using the reduction to absur-dity.