Optimal batch codes: Many items or low retrieval requirement

Previous Article
On linear equivalence and Phelps codes. Addendum
AMC Home
This Issue
Next Article
New nearly optimal codebooks from relative difference sets

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

Abstract
Related Papers

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.
[2]	S. Bhattacharya, S. Ruj and B. Roy, Combinatorial batch codes: A lower bound and optimal constructions,, preprint, ().
[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.
[4]	Cs. Bujtás and Zs. Tuza, Combinatorial batch codes: Extremal problems under Hall-type conditions, Electronic Notes Discrete Math., (2011), to appear.
[5]	Cs. Bujtás and Zs. Tuza, Optimal combinatorial batch codes derived from dual systems, Miskolc Math. Notes (2011), to appear.
[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.
[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.

show all references

References:

[1]	C. Berge, "Hypergraphs,'' North-Holland, Amsterdam, 1989.
[2]	S. Bhattacharya, S. Ruj and B. Roy, Combinatorial batch codes: A lower bound and optimal constructions,, preprint, ().
[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.
[4]	Cs. Bujtás and Zs. Tuza, Combinatorial batch codes: Extremal problems under Hall-type conditions, Electronic Notes Discrete Math., (2011), to appear.
[5]	Cs. Bujtás and Zs. Tuza, Optimal combinatorial batch codes derived from dual systems, Miskolc Math. Notes (2011), to appear.
[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.
[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.

[1]	Xu Zhang, Xiang Li. Modeling and identification of dynamical system with Genetic Regulation in batch fermentation of glycerol. Numerical Algebra, Control and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2021, 17 (4) : 1845-1861. doi: 10.3934/jimo.2020049
[7]	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
[8]	Zsolt Saffer, Wuyi Yue. A dual tandem queueing system with GI service time at the first queue. Journal of Industrial and Management Optimization, 2014, 10 (1) : 167-192. doi: 10.3934/jimo.2014.10.167
[9]	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
[10]	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
[11]	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
[12]	Vladimir Pozdyayev. 2D system analysis via dual problems and polynomial matrix inequalities. Numerical Algebra, Control and Optimization, 2016, 6 (4) : 491-504. doi: 10.3934/naco.2016022
[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 and 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 and 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

Other articles
by authors

on AIMS
Csilla Bujtás Zsolt Tuza
on Google Scholar
Csilla Bujtás Zsolt Tuza

[Back to Top]