Pliable Index COding: Novel lower bound on the fraction of satisfied clients with a single transmission and its application
Pliable Index COding: Novel lower bound on the fraction of satisfied clients with a single transmission and its application
复制标题
柔韧指数编码：对单次传输及其应用感到满意的客户比例的新下限
DOI：
10.1109/itw.2016.7606849
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Daniela Tuninetti
中科院分区：
文献类型：
--
作者：
Tang Liu;Daniela Tuninetti
这项工作研究了柔韧指数编码问题（PICOD），一个经典的索引编码问题的变化，客户端是满意的，如果它可以成功地解码至少一个消息不存在于其侧信息集。PICOD对“内容类型编码”应用程序（如Web搜索）进行建模。PICOD在以下意义上与经典索引编码（其中每个客户端期望不存在于其辅助信息集中的特定消息）显著不同。过去的工作表明，对于PICOD，O（log n）广播传输足以满足所有n个客户端，而不是索引编码所需的Ω（n）传输;传输数量的这种指数改进的关键是一个概率参数，以表明单个传输可以满足至少一个恒定比例的客户端。本文进一步阐述了这一关键结果如下。(i)非概率分析提供了在所有边信息集具有相同基数的情况下，可以由单次传输满足的PICOD客户端的最大部分的不小于1/e的下限;对于任何数量的消息和客户端，新的界限比已知的界限更紧，并且揭示了边信息集的基数如何影响单个传输所满足的客户端的数量。(ii)相同的论证适用于消息在任何给定客户端的边信息集中的情况，其中概率p ∈（0，1）独立于所有其他消息和客户端，并且当存在足够多的消息时，提供了比已知结果更精细的性能表征。
This work studies the Pliable Index CODing problem (PICOD), a variation of the classical index coding problem where a client is satisfied if it can successfully decode at least one massage not present in its side information set. PICOD models `content-type coding' applications, such as web searches. PICOD significantly differs from classical index coding (where each client desires a specific message not present in its side information set) in the following sense. Past work showed that for PICOD O(log n) broadcast transmissions suffice to satisfy all the n clients, as opposed to the Ω(n) transmissions required by index coding; the key to this exponential improvement in number of transmissions is a probabilistic argument to show that a single transmission can satisfy at least a constant fraction of the clients. This paper elaborates further on this key result as follows. (i) A non-probabilistic analysis provides a lower bound, no smaller than 1/e, on the largest fraction of PICOD clients that can be satisfied by a single transmission in the case where all side information sets have the same cardinality; the new bound is tighter than known ones for any number of messages and clients, and sheds light into how the cardinality of the side information sets affects the number of clients satisfied by a single transmission. (ii) The same argument applied to the case where a message is in the side information set of any given client with probability p ∈ (0, 1) independent of all other messages and clients, and when there are sufficiently many messages, provides an more refined characterization of the performance than known results.