Back to Search Start Over

Batch Codes Through Dense Graphs Without Short Cycles.

Authors :
Rawat, Ankit Singh
Song, Zhao
Dimakis, Alexandros G.
Gal, Anna
Source :
IEEE Transactions on Information Theory. Apr2016, Vol. 62 Issue 4, p1592-1604. 13p.
Publication Year :
2016

Abstract

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 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 graph-theoretic 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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
00189448
Volume :
62
Issue :
4
Database :
Academic Search Index
Journal :
IEEE Transactions on Information Theory
Publication Type :
Academic Journal
Accession number :
113872621
Full Text :
https://doi.org/10.1109/TIT.2016.2524007