A New Combinatorial Batch Code

Batch code was introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai in 2004. A batch code specifies a method to resolve problem about information retrieval. The question is how to distribute a database of n items among m devices (servers) in such a way that when we need any k items among the n items, we can read at most t items from each server to find them, and we want the total storage N as small as possible.We study the special case t=1, Ishai, Kushilevitz, Ostrovsky, and Sahai gave the definition of CBC. And each server can be represented as a subset of the set of n elements, the problem of constructing such codes falls naturally within a combinatorial framework. We call these code "combinatorial batch code (CBC)". Paterson, Stinson, and Wei gave the definition of combinatorial batch code, also gave a method to judge whether the code is CBC and the construction of some optimal CBC. In this thesis, we mainly study the new CBC with the same number of elements in each server, suppose each server have a elements, we call this CBC as ECBC. We also will give the definition of optimal ECBC, and denote the corresponding value of m by m(n, a, k). In this thesis, we focus on the ECBC with a= 2,3 and their construction. Meanwhile we will prove that when l≥2,k≥2, the (m+l,m+l+k-1,k, m)-CBC does not exit, which provide some reference for future work in this area.There are four chapters in the thesis:In the first chapter, we will introduce the background of CBC, the definition and known results. Meanwhile, we will give the important lemma.In the second chapter, we will give the construction of the optimal ECBC with a=2 and the optimal ECBC with a= 3 for small value of n. Then we use recursion method to give the value of m(n,2, k) and an upper bound of m(n,3,3).In the third chapter, we improve the previous method to prove the (m+l,m+l+ k-1,k, m)-CBC is non-existent to provide some reference for future work in this area.In the fourth chapter, we will present the conclusions and the future work.