Batch Codes Through Dense Graphs Without Short Cycles
Batch Codes Through Dense Graphs Without Short Cycles
复制标题
通过密集图批量编码，无需短周期
DOI：
10.1109/tit.2016.2524007
复制
发表时间：
2016
影响因子：
2.5
通讯作者：
Anna Gál
中科院分区：
文献类型：
--
作者：
A. Rawat;Zhao Song;A. Dimakis;Anna Gál
考虑需要使用m个服务器存储的n个数据项的大型数据库。我们研究如何对信息进行编码，以便可以并行执行大量k个读取请求，同时速率保持恒定（理想情况下接近1）。这个问题是等价于设计的多集批处理代码介绍了Ishai等人。我们给出了家庭的多集批处理代码的渐近最优率的形式1-1/poly（k）和服务器的数量m缩放多项式的数量k的读取请求。一个优势，我们的批处理代码的建设，以前已知的多集批处理代码是明确的和确定性的解码算法和渐近最优容错。我们的主要技术创新是一个图论方法设计多集批处理代码使用密集的二分图，没有小圈。我们修改之前的密集，高围长图的图形构造，以获得我们的批处理代码的结果。我们实现了接近最佳的权衡参数的二分图为基础的批处理代码。
Consider a large database of n data items that need to be stored using m servers. We study how to encode information so that a large number k of read requests can be performed in parallel, while the rate remains constant (and ideally approaches one). This problem is equivalent to the design of multiset batch codes introduced by Ishai et al. We give the families of multiset batch codes with asymptotically optimal rates of the form 1-1/poly(k) and a number of servers m scaling polynomially in the number of read requests k. An advantage of our batch code constructions over most previously known multiset batch codes is explicit and deterministic decoding algorithms and asymptotically optimal fault tolerance. Our main technical innovation is a graphtheoretic method of designing multiset batch codes using dense bipartite graphs with no small cycles. We modify prior graph constructions of dense, high-girth graphs to obtain our batch code results. We achieve close-to-optimal tradeoffs between the parameters for bipartite graph-based batch codes.