Batch code[1]
Description
Binary code designed for minimizing the total amount of storage and the worst-case maximal load on any devices in a distributed system.
An \((n,N,k,m,t)\) batch code encodes a length-\(n\) string \(x_1,\cdots,x_n\) into an \(m\)-tuple of strings of total length \(N\) (are also called buckets), such that for each \(k\)-tuple of distinct indices \(i_1,i_2,...,i_k\), the entries \(x_{i_1},...,x_{i_k}\) can be decoded by reading at most \(t\) symbols from each bucket. If each bucket of a batch code contains a single symbol, then the \((n,N,k,m)\) batch code is primitive.
If, for any multiset \(i_1, i_2, ..., i_k \in [n]\), there is a partition of buckets into subsets \(S_1, ..., S_k \subset [m]\) such that each \(x_{i_j}\) can be recovered by reading at most one symbol from each bucket in \(S_j\), then the \((n, N, k, m)\) code is a multiset batch code.
Protection
The Gadget Lemma states that any \((n,N,k,m)\) batch code at \(t=1\) can be transformed into a multiset \((rn,rN,k,m)\) for any positive integer \(r\) [2].
Combining two batch codes \(C_1\) and \(C_2\), which are \((n_1,N_1,k_1,m_1)\) and \((n_2,N_2,k_2,m_2)\) batch codes respectively, yields a composite batch code \(C_1\otimes C_2\), which is an \((n_1, m_1N_2, k_1 k_2, m_1 m_2)\) batch code.
Notes
Parent
Cousins
- Locally recoverable code (LRC) — A systematic batch code with restricted size of reconstruction sets can recover any query of \(t\) information symbols with recovery sets of size \(r\) [4,5].
- Locally decodable code (LDC) — Batch codes and LDCs are related [1,6][3; Ch. 10.3].
- \([2^r-1,2^r-r-1,3]\) Hamming code — Hamming codes can be used to construct batch codes [7][3; Exam. 10.9].
- Generalized RM (GRM) code — GRM codes can be used to construct batch codes [7].
- Multiplicity code — Multiplicity codes can be used to construct batch codes [8].
- Private information retrieval (PIR) code — Batch and PIR codes are related [6,9].
References
- [1]
- Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai, “Batch codes and their applications”, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (2004) DOI
- [2]
- A. S. Rawat, Z. Song, A. G. Dimakis, and A. Gal, “Batch Codes Through Dense Graphs Without Short Cycles”, IEEE Transactions on Information Theory 62, 1592 (2016) DOI
- [3]
- I. F. Blake, Essays on Coding Theory (Cambridge University Press, 2024) DOI
- [4]
- V. Skachek, “Batch and PIR Codes and Their Connections to Locally Repairable Codes”, Signals and Communication Technology 427 (2018) DOI
- [5]
- A.-E. Riet, V. Skachek, and E. K. Thomas, “Batch Codes for Asynchronous Recovery of Data”, IEEE Transactions on Information Theory 68, 1545 (2022) DOI
- [6]
- R. Henry, “Polynomial Batch Codes for Efficient IT-PIR”, Proceedings on Privacy Enhancing Technologies 2016, 202 (2016) DOI
- [7]
- T. Baumbaugh, Y. Diaz, S. Friesenhahn, F. Manganiello, and A. Vetter, “Batch Codes from Hamming and Reed-Müller Codes”, (2017) arXiv:1710.07386
- [8]
- H. Asi and E. Yaakobi, “Nearly Optimal Constructions of PIR and Batch Codes”, (2017) arXiv:1701.07206
- [9]
- V. Skachek, “Batch and PIR Codes and Their Connections to Locally Repairable Codes”, (2017) arXiv:1611.09914
Page edit log
- Victor V. Albert (2024-08-18) — most recent
- Victor V. Albert (2022-07-07)
- Yijia Xu (2022-04-25)
Cite as:
“Batch code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/batch