American Institute of Mathematical Sciences

Advanced
August  2011, 5(3): 529-541. doi: 10.3934/amc.2011.5.529

Optimal batch codes: Many items or low retrieval requirement

Csilla Bujtás 1, and  Zsolt Tuza 2,

1. 

Department of Computer Science and Systems Technology, University of Pannonia, Egyetem u. 10, Veszprém, H-8200, Hungary
2. 

Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 13-17, Budapest, H-1111, Hungary

Received  December 2010 Revised  May 2011 Published  August 2011

Combinatorial batch codes were introduced by Ishai et al. [36th ACM STOC (2004), 262-271] and studied in detail by Paterson et al. [Adv. Math. Commun., 3 (2009), 13-27] for the purpose of distributed storage and retrieval of items of a database on a given number of servers in an economical way. A combinatorial batch code with parameters $n,k,m,t$ means that $n$ items are stored on $m$ servers such that any $k$ different items can be retrieved by reading out at most $t$ items from each server. If $t=1$, this can equivalently be represented with a family $\mathcal F$ of $n$ not necessarily distinct sets over an $m$-element underlying set, such that the union of any $i$ members of $\mathcal F$ has cardinality at least $i$, for every $1\le i\le k$. The goal is to determine the minimum $N(n,k,m)$ of $\sum$$F\in\mathcal F$$|F|$ over all combinatorial batch codes $\mathcal F$ with given parameters $n,k,m$ and $t=1$.
   We prove $N(n,k,m)= (k-1)n- \lfloor \frac{(k-1){m \choose k-1}-n}{m-k+1} \rfloor$ for all ${m\choose k-2} \le n \le (k-1){m\choose k-1}$. Together with the results of Paterson et al. for $n$ larger, this completes the determination of $N(n,3,m)$. We also compute $N(n,4,m)$ in the entire range $n\ge m\ge 4$. Several types of code transformations keeping optimality are described, too.
Keywords: system of distinct representatives., dual system, Batch code, hypergraph.
Mathematics Subject Classification: Primary: 05A05, 05C65, 05D05, 68P20, 68R0.
Citation: Csilla Bujtás, Zsolt Tuza. Optimal batch codes: Many items or low retrieval requirement. Advances in Mathematics of Communications, 2011, 5 (3) : 529-541. doi: 10.3934/amc.2011.5.529
References:
[1]

C. Berge, "Hypergraphs,'' North-Holland, Amsterdam, 1989.  Google Scholar

[2]

S. Bhattacharya, S. Ruj and B. Roy, Combinatorial batch codes: A lower bound and optimal constructions,, preprint, ().   Google Scholar

[3]

R. A. Brualdi, K. P. Kiernan, S. A. Meyer and M. W. Schroeder, Combinatorial batch codes and transversal matroids, Adv. Math. Commun., 4 (2010), 419-431; Corrigendum, Adv. Math. Commun., 4 (2010), 597 pp.  Google Scholar

[4]

Cs. Bujtás and Zs. Tuza, Combinatorial batch codes: Extremal problems under Hall-type conditions, Electronic Notes Discrete Math., (2011), to appear. Google Scholar

[5]

Cs. Bujtás and Zs. Tuza, Optimal combinatorial batch codes derived from dual systems, Miskolc Math. Notes (2011), to appear. Google Scholar

[6]

Y. Ishai, E. Kushiletitz, R. Ostrovsky and A. Sahai, Batch codes and their applications, in "Proceedings of the 36th Annual ACM Symposium on Theory of Computing,'' ACM Press, New York, (2004), 262-271.  Google Scholar

[7]

M. B. Paterson, D. R. Stinson and R. Wei, Combinatorial batch codes, Adv. Math. Commun., 3 (2009), 13-27. doi: 10.3934/amc.2009.3.13.  Google Scholar

show all references

References:
[1]

C. Berge, "Hypergraphs,'' North-Holland, Amsterdam, 1989.  Google Scholar

[2]

S. Bhattacharya, S. Ruj and B. Roy, Combinatorial batch codes: A lower bound and optimal constructions,, preprint, ().   Google Scholar

[3]

R. A. Brualdi, K. P. Kiernan, S. A. Meyer and M. W. Schroeder, Combinatorial batch codes and transversal matroids, Adv. Math. Commun., 4 (2010), 419-431; Corrigendum, Adv. Math. Commun., 4 (2010), 597 pp.  Google Scholar

[4]

Cs. Bujtás and Zs. Tuza, Combinatorial batch codes: Extremal problems under Hall-type conditions, Electronic Notes Discrete Math., (2011), to appear. Google Scholar

[5]

Cs. Bujtás and Zs. Tuza, Optimal combinatorial batch codes derived from dual systems, Miskolc Math. Notes (2011), to appear. Google Scholar

[6]

Y. Ishai, E. Kushiletitz, R. Ostrovsky and A. Sahai, Batch codes and their applications, in "Proceedings of the 36th Annual ACM Symposium on Theory of Computing,'' ACM Press, New York, (2004), 262-271.  Google Scholar

[7]

M. B. Paterson, D. R. Stinson and R. Wei, Combinatorial batch codes, Adv. Math. Commun., 3 (2009), 13-27. doi: 10.3934/amc.2009.3.13.  Google Scholar

[1]

Xu Zhang, Xiang Li. Modeling and identification of dynamical system with Genetic Regulation in batch fermentation of glycerol. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 393-403. doi: 10.3934/naco.2015.5.393
[2]

Tao Jiang, Liwei Liu. Analysis of a batch service multi-server polling system with dynamic service control. Journal of Industrial & Management Optimization, 2018, 14 (2) : 743-757. doi: 10.3934/jimo.2017073
[3]

Chongyang Liu, Zhaohua Gong, Enmin Feng, Hongchao Yin. Modelling and optimal control for nonlinear multistage dynamical system of microbial fed-batch culture. Journal of Industrial & Management Optimization, 2009, 5 (4) : 835-850. doi: 10.3934/jimo.2009.5.835
[4]

Omer Faruk Yilmaz, Mehmet Bulent Durmusoglu. A performance comparison and evaluation of metaheuristics for a batch scheduling problem in a multi-hybrid cell manufacturing system with skilled workforce assignment. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1219-1249. doi: 10.3934/jimo.2018007
[5]

Bangyu Shen, Xiaojing Wang, Chongyang Liu. Nonlinear state-dependent impulsive system in fed-batch culture and its optimal control. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 369-380. doi: 10.3934/naco.2015.5.369
[6]

Wenjuan Zhao, Shunfu Jin, Wuyi Yue. A stochastic model and social optimization of a blockchain system based on a general limited batch service queue. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1845-1861. doi: 10.3934/jimo.2020049
[7]

Zsolt Saffer, Wuyi Yue. A dual tandem queueing system with GI service time at the first queue. Journal of Industrial & Management Optimization, 2014, 10 (1) : 167-192. doi: 10.3934/jimo.2014.10.167
[8]

Masaaki Harada, Takuji Nishimura. An extremal singly even self-dual code of length 88. Advances in Mathematics of Communications, 2007, 1 (2) : 261-267. doi: 10.3934/amc.2007.1.261
[9]

Vladimir Pozdyayev. 2D system analysis via dual problems and polynomial matrix inequalities. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 491-504. doi: 10.3934/naco.2016022
[10]

M. De Boeck, P. Vandendriessche. On the dual code of points and generators on the Hermitian variety $\mathcal{H}(2n+1,q^{2})$. Advances in Mathematics of Communications, 2014, 8 (3) : 281-296. doi: 10.3934/amc.2014.8.281
[11]

Sihuang Hu, Gabriele Nebe. There is no $[24,12,9]$ doubly-even self-dual code over $\mathbb F_4$. Advances in Mathematics of Communications, 2016, 10 (3) : 583-588. doi: 10.3934/amc.2016027
[12]

Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032
[13]

Yu Tian, John R. Graef, Lingju Kong, Min Wang. Existence of solutions to a multi-point boundary value problem for a second order differential system via the dual least action principle. Conference Publications, 2013, 2013 (special) : 759-769. doi: 10.3934/proc.2013.2013.759
[14]

María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021018
[15]

Martino Borello, Francesca Dalla Volta, Gabriele Nebe. The automorphism group of a self-dual $[72,36,16]$ code does not contain $\mathcal S_3$, $\mathcal A_4$ or $D_8$. Advances in Mathematics of Communications, 2013, 7 (4) : 503-510. doi: 10.3934/amc.2013.7.503
[16]

Zhongming Chen, Liqun Qi. Circulant tensors with applications to spectral hypergraph theory and stochastic process. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1227-1247. doi: 10.3934/jimo.2016.12.1227
[17]

Jean-Marc Hérard, Olivier Hurisse. Some attempts to couple distinct fluid models. Networks & Heterogeneous Media, 2010, 5 (3) : 649-660. doi: 10.3934/nhm.2010.5.649
[18]

Johan Chrisnata, Han Mao Kiah, Sankeerth Rao Karingula, Alexander Vardy, Eitan Yaakobi Yao, Hanwen Yao. On the number of distinct k-decks: Enumeration and bounds. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021032
[19]

Thomas Feulner. The automorphism groups of linear codes and canonical representatives of their semilinear isometry classes. Advances in Mathematics of Communications, 2009, 3 (4) : 363-383. doi: 10.3934/amc.2009.3.363
[20]

Anton Zorich. Explicit Jenkins-Strebel representatives of all strata of Abelian and quadratic differentials. Journal of Modern Dynamics, 2008, 2 (1) : 139-185. doi: 10.3934/jmd.2008.2.139

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (72)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences