Combinatorial batch codes: a lower bound and optimal constructions

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

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 (13)

• Batch Codes from Hamming and Reed-M\"uller Codes
• Batch codes from affine Cartesian codes and quotient spaces
• Linear Batch Codes
• The results on optimal values of some combinatorial batch codes
• Optimal combinatorial batch codes based on block designs
• On an extremal hypergraph problem related to combinatorial batch codes
• Turán numbers and batch codes
• Multiset combinatorial batch codes
• Derandomized Construction of Combinatorial Batch Codes
• Some optimal combinatorial batch codes with \(k=5\)
• Constructions and bounds for batch codes with small parameters
• Fractional Repetition and Erasure 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)