Combinatorial Batch Codes: A Lower Bound and Optimal Constructions

Details Combinatorial Batch Codes: A Lower Bound and Optimal Constructions Combinatorial Batch Codes: A Lower Bound and Optimal Constructions

2011-02-24

arxiv.org/abs/1102.4951v1

Computer Science

Discrete Mathematics

Scientific paper

Batch codes, introduced by Ishai, Kushilevitz, Ostrovsky and Sahai in [1], are methods for solving the following data storage problem: n data items are to be stored in m servers in such a way that any k of the n items can be retrieved by reading at most t items from each server, and that the total number of items stored in m servers is N . A Combinatorial batch code (CBC) is a batch code where each data item is stored without change, i.e., each stored data item is a copy of one of the n data items. One of the basic yet challenging problems is to find optimal CBCs, i.e., CBCs for which total storage (N) is minimal for given values of n, m, k, and t. In [2], Paterson, Stinson and Wei exclusively studied CBCs and gave constructions of some optimal CBCs. In this article, we give a lower bound on the total storage (N) for CBCs. We give explicit construction of optimal CBCs for a range of values of n. For a different range of values of n, we give explicit construction of optimal and almost optimal CBCs. Our results partly settle an open problem of [2].

Affiliated with

Also associated with

No associations

Rating

Combinatorial Batch Codes: A Lower Bound and Optimal Constructions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Combinatorial Batch Codes: A Lower Bound and Optimal Constructions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial Batch Codes: A Lower Bound and Optimal Constructions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-86447