Combinatorial batch codes: a lower bound and optimal constructions

DOI10.3934/AMC.2012.6.165zbMATH Open1244.05219arXiv1102.4951OpenAlexW2963487294MaRDI QIDQ444518FDOQ444518

Authors: Srimanta Bhattacharya, Sushmita Ruj, Bimal Roy 

Publication date: 14 August 2012

Published in: Advances in Mathematics of Communications (Search for Journal in Brave)

Abstract: 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].

Full work available at URL: https://arxiv.org/abs/1102.4951

Recommendations

• Optimal combinatorial batch codes based on block designs
• Combinatorial batch codes
• Optimal batch codes: many items or low retrieval requirement
• The results on optimal values of some combinatorial batch codes
• Multiset combinatorial batch codes

zbMATH Keywords

Hall's theorembinary constant weight codescombinatorial batch codes

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Combinatorial codes (94B25) Extremal set theory (05D05)

Cited In (20)

• Batch codes from affine Cartesian codes and quotient spaces
• Combinatorial batch codes and transversal matroids
• The results on optimal values of some combinatorial batch codes
• Optimal combinatorial batch codes based on block designs
• Derandomized construction of combinatorial batch codes
• Batch codes from Hamming and Reed-Muller codes
• Combinatorial batch codes based on RTD\((q-2, q)\)
• A special kind of combinatorial batch codes
• On an extremal hypergraph problem related to combinatorial batch codes
• Turán numbers and batch codes
• Multiset combinatorial batch codes
• Fractional repetition and erasure batch codes
• A class of combinatorial batch code based on the \(p\) construction
• Optimal batch codes: many items or low retrieval requirement
• Linear batch codes
• Combinatorial batch codes
• Some optimal combinatorial batch codes with \(k=5\)
• Constructions and bounds for batch codes with small parameters
• On erasure combinatorial batch codes
• Combinatorial batch codes: extremal problems under Hall-type conditions

This page was built for publication: Combinatorial batch codes: a lower bound and optimal constructions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q444518)