Embedded Index Coding
Embedded Index Coding
复制标题
DOI：
10.1109/tit.2020.3043767
复制
发表时间：
2021-03-01
影响因子：
2.5
通讯作者：
Wootters, Mary
中科院分区：
文献类型：
--
作者：
Porter, Alexandra;Wootters, Mary
受分布式存储和分布式计算应用的启发，我们引入了嵌入式索引编码（EIC）。EIC是一种分布式索引编码，其中分布式系统中的节点同时充当信息的广播发送者和接收者。我们展示了线性嵌入索引编码与一般线性索引编码的关系，并给出了最优嵌入索引编码的通信代价的表征和界限。我们还定义了基于任务的EIC，其中只有一个发送方节点负责将块发送到特定的接收节点。基于任务的EIC在计算上更易于处理，并且在分布式存储等应用中具有优势，在分布式存储中，发送者可能在不同时间完成广播。最后，我们给出了逼近最优线性嵌入索引码的启发式算法，并通过经验证明了这些算法的良好性能。
Motivated by applications in distributed storage and distributed computation, we introduce embedded index coding (EIC). EIC is a type of distributed index coding in which nodes in a distributed system act as both broadcast senders and receivers of information. We show how linear embedded index coding is related to linear index coding in general, and give characterizations and bounds on the communication costs of optimal embedded index codes. We also define task-based EIC, in which there is only one sender node responsible for transmitting a block to a particular receiving node. Task-based EIC is more computationally tractable and has advantages in applications such as distributed storage, in which senders may complete their broadcasts at different times. Finally, we give heuristic algorithms for approximating optimal linear embedded index codes, and demonstrate empirically that these algorithms perform well.