Combinatorial batch codes: a lower bound and optimal constructions

DOI10.3934/AMC.2012.6.165MaRDI QIDQ444518zbMATH OpenOpenAlexFDO

Authors Srimanta Bhattacharya, Sushmita Ruj, Bimal Roy

Publication date 14 August 2012

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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

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

Cited in

(20)

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

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)