Almost Optimal Construction of Functional Batch Codes Using Extended Simplex Codes
Lev Yohananov, Eitan Yaakobi · IEEE Transactions on Information Theory · 2022
Afunctional$k$-batchcode of dimension$s$consists of$n$servers storing linear combinations of$s$linearly independent information bits. Any multiset request of size$k$of linear combinations (or requests) of the information bits can be recovered by$k$disjoint subsets of the servers. The goal under this paradigm is to find the minimum number of servers for given values of$s$and$k$. A recent conjecture states that for any$k=2^{s-1}$requests the optimal solution requires$2^{s}-1$servers. This conjecture is verified for$s \leqslant 5$but previous work could only show that codes with$n=2^{s}-1$servers can support a solution for$k=2^{s-2} + 2^{s-4} + \left \lfloor{ \frac { 2^{s/2}}{\sqrt {24}} }\right \rfloor $requests. This paper reduces this gap and shows the existence of codes for$k=\lfloor \frac {5}{6}2^{s-1} \rfloor - s$requests with the same number of servers. Another construction in the paper provides a code with$n=2^{s+1}-2$servers and$k=2^{s}$requests, which is an optimal result. These constructions are mainly based on extended Simplex codes and equivalently provide constructions forparallel Random I/O (RIO)codes.