Abstract
Erasure combinatorial batch codes are a family of codes for distributed storage systems which not only allow for the retrieval of any set of a limited number of items even in presence of server failures, but also balance the load among the servers when retrieving. To present new constructions is one of the objectives of studying erasure combinatorial batch codes. Nonadaptive group testing has many applications to various fields such as DNA library screening and multi-access communications, etc. A lot of constructions of nonadaptive group testing have been given by many authors. In this paper, based on nonadaptive group testing, we obtain three classes of erasure combinatorial batch codes.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bai Y., Huang T., Wang K.: Error-correcting pooling designs associated with some distance-regular graphs. Discret. Appl. Math. 157, 3038–3045 (2009).
Balachandran N., Bhattacharya S.: On an extremal hypergraph problem related to combinatorial batch codes. Discret. Appl. Math. 162, 373–380 (2014).
Brualdi R.A., Kiernan K.P., Meyer S.A., Schroeder M.W.: Combinatorial batch codes and transversal matroids. Adv. Math. Commun. 4, 419–431 (2010).
Bujtás C., Tuza Z.: Optimal batch codes: many items or low retrieval requirement. Adv. Math. Commun. 5, 529–541 (2011).
Bujtás C., Tuza Z.: Optimal combinatorial batch codes derived from dual systems. Miskolc Math. Notes 12, 11–23 (2011).
Bujtás C., Tuza Z.: Turán numbers and batch codes. Discret. Appl. Math. 186, 45–55 (2015).
Chen J., Zhang S., Zhang G.: Optimal combinatorial batch code: monotonicity, lower and upper bounds. Sci. Sin. Math. 45, 311–320 (2015). (in Chinese).
Du D., Hwang F.K.: Pooling designs and nonadaptive group testing, important tools for DNA sequencing. In: Series on Applied Mathematics, vol. 18, World Scientific, Hackensack (2006).
Gao S., Li Z., Wu W., Pardalos P.M., Du D.: Group testing with geometry of classical groups over finite fields. J. Algebr. Comb. (2018). https://doi.org/10.1007/s10801-018-0828-0.
Guo J., Wang K.: A construction of pooling designs with surprisingly high degree of error correction. J. Combin. Theory Ser. A 118, 2056–2058 (2011).
Huang T., Weng C.: Pooling spaces and nonadaptive pooling designs. Discret. Math. 282, 163–169 (2004).
Ishai Y., Kushilevitz E., Ostrovsky R., Sahai A.: Batch codes and their applications. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing STOC’ 04, New York, USA, vol. 36, pp. 262–271 (2004).
Jia D., Zhang G., Yuan L.: A class of optimal combinatorial batch code. Acta Math. Sin. Chin. Ser. 59, 267–278 (2016). (in Chinese).
Jung J.Y., Mummert C., Niese E., Schroeder M.: On erasure combinatorial batch codes. Adv. Math. Commun. 12, 49–65 (2018).
Macula A.J.: A simple construction of \(d\)-disjunct matrices with certain constant weights. Discret. Math. 162, 311–312 (1996).
Ngo H., Du D.: New constructions of nonadaptive and error-tolerance pooling designs. Discret. Math. 243, 161–170 (2002).
Paterson M.B., Stinson D.R., Wei R.: Combinatorial batch codes. Adv. Math. Commun. 3, 13–27 (2009).
Shen Y., Jia D., Zhang G.: The results on optimal values of some combinatorial batch codes. Adv. Math. Commun. 12, 681–690 (2018).
Silberstein N.: Fractional repetition and erasure batch codes. In: Coding Theory and Applications, CIM Ser. Math. Sci., vol. 3, pp. 335–343. Springer, Cham (2015).
Silberstein N., Gál A.: Optimal combinatorial batch codes based on block designs. Des. Codes Cryptogr. 78, 409–424 (2016).
Wolf J.K.: Born again group testing: multiaccess communications. IEEE Trans. Inf. Theory IT–31, 185–191 (1985).
Zhang G., Li B., Sun X., Li F.: A construction of \(d^z\)-disjunct matrices in a dual space of symplectic space. Discret. Appl. Math. 156, 2400–2406 (2008).
Zhang G., Sun X., Li B.: Error-correcting pooling designs associated with the dual space of unitary space and ratio efficiency comparison. J. Comb. Optim. 18, 51–63 (2009).
Zhang G., Yang Y., Zhao X.: A construction of \(d^z\)-disjunct matrices by orthogonal space and discussion on their design parameters. Discret. Math. 309, 6026–6034 (2009).
Acknowledgements
The authors would like to thank the referees and editors for their valuable suggestions which have helped improve this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by C. J. Colbourn.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This research is partially supported by National Natural Science Foundation of China (Grant No. 11571091), and Natural Science Foundation of Hebei Education Department (Grant No. ZD2016096)
Rights and permissions
About this article
Cite this article
Jia, D., Zhang, S. & Zhang, G. Erasure combinatorial batch codes based on nonadaptive group testing. Des. Codes Cryptogr. 87, 1647–1656 (2019). https://doi.org/10.1007/s10623-018-0564-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-018-0564-4