A survey of the study of combinatorial batch code

Abstract

A combinatorial batch code has strong practical motivation in the distributed storage and retrieval of data in a database. In this survey, we give a brief introduction to the combinatorial batch codes and some progress.

Keywords

Combinatorial batch codes / optimal CBC / uniform CBC / set system

References

[1] Balachandran N, Bhattacharya S. On an extremal hypergraph problem related to combinatorial batch codes. Discrete Appl Math 2014; 162: 373–380

[2] Bhattacharya S, Ruj S, Roy B. Combinatorial batch codes: a lower bound and optimal constructions. Adv Math Comm 2012; 6(2): 165–174

[3] Brualdi R A, Kiernan K P, Meyer S A, Schroeder M W. Combinatorial batch codes and transversal matroids. Adv Math Comm 2010; 4: 419–431

[4] Brualdi R A, Kiernan K P, Meyer S A, Schroeder M W. Erratum to “Combinatorial batch codes and transversal matroids”. Adv In Math Comm 2010; 4(3): 597

[5] Bujtás C, Tuza Z. Combinatorial batch codes: extremal problems under Hall-type conditions. Electron Notes Discrete Math 2011; 38: 201–206

[6] Bujtás C, Tuza Z. Optimal batch codes: many items or low retrieval requirement. Adv Math Comm 2011; 5(3): 529–541

[7] Bujtás C, Tuza Z. Optimal combinatorial batch codes derived from dual systems. Miskolc Math Notes 2011; 12(1): 11–23

[8] Bujtás C, Tuza Z. Relaxations of Hall’s condition: optimal batch codes with multiple queries. Appl Anal Discrete Math 2012; 6(1): 72–81

[9] Bujtás C, Tuza Z. Turán numbers and batch codes. Discrete Appl Math 2015; 186: 45–55

[10] Chen J F, Zhang S M, Zhang G S. Optimal combinatorial batch code: monotonicity, lower and upper bounds. Sci Sin Math 2015; 45(3): 311–320

[11] ChenS B. A New Combinatorial Batch Code. Master Thesis. Beijing: Beijing Jiaotong University, 2010 (in Chinese)

[12] IshaiYKushilevitzEOstrovskyRSahaiA. Batch codes and their applications, In: STOC’04 (Proceedings of the 36th Annual ACM Symposium on Theory of Computing). New York, 2004, 262–271

[13] Jia D D, Zhang G S, Yuan L D. A class of optimal combinatorial batch code. Acta Math Sin, Chin Ser 2016; 59(2): 267–278

[14] Liu X, Zhang S M, Zhang G S. Combinatorial batch codes based on RTD (q−2, q). Adv Math (China) 2016; 45(5): 700–710

[15] Patterson M B, Stinson D R, Wei R. Combinatorial batch codes. Adv Math Comm 2009; 3(1): 13–27

[16] RujSRoyB. More on combinatorial batch codes. arXiv: 0809.3357v1

[17] Silberstein N, Gál A. Optimal combinatorial batch codes based on block designs. Des Codes and Cryptogr 2016; 78: 409–424

RIGHTS & PERMISSIONS

Higher Education Press 2023