Open Access Publications from the University of California

Content-Type Coding

• Author(s): Song, Linqi;
Our research indicates that in some cases, these benefits can be significant. We design a polynomial-time algorithm for pliable index coding that requires at most $O(\log^2(n))$ broadcast transmissions to serve $n$ clients, as compared to $O(n)$ broadcast transmissions for conventional index coding. This indicates that the exponential benefits of pliable index coding can be effectively realized. Moreover, we explore two applications: recommender systems and distributed computing. In recommender systems, we ask: how much we can gain in terms of bandwidth and user satisfaction, if recommender systems took into account not only the user preferences, but also the fact that they may need to serve these users under bandwidth constraints, as is the case over wireless networks. In other words, what if the recommender systems became bandwidth aware? In this setup, the user is satisfied to receive any message she does not already have, with a satisfaction proportional to her preference for that message. We show, through a number of scenaria, that although the optimization problems are in general NP-hard, polynomial time algorithms with constant approximation ratio can be designed to achieve more than 80\% of the satisfaction and to save 90\% of bandwidth. In distributed computing, to improve the communication efficiency in the data shuffling phase, we examine the pliable index coding problem under data shuffling constraints, where each of the $m$ messages can satisfy at most $c$ out of $n$ clients. We show that the constrained pliable index coding can achieve up to $O(n)$ (best case) benefits over index coding. We prove that the problem is NP-hard and the optimal broadcast transmissions for random instances is almost surely upper bounded by $O(\min\{\frac{n}{c\log(n)},\frac{n}{\log(m)}\})$ for $c=o(\frac{n^{1/7}}{\log^2(n)})$ and $O(\min\{\frac{n}{c}+\log(c),\frac{n}{\log(m)}\})$ for $c=\Omega(\frac{n^{1/7}}{\log^2(n)})$. Building upon constrained pliable index coding, we design a hierarchical data shuffling scheme for distributed computing. By leveraging the many possible shuffling choices, our proposed shuffling scheme is able to reduce the communication cost and achieve benefits up to $O(ns/m)$ over the index coding method, where $ns/m$ is the average number of workers caching a message, and $m$, $n$, and $s$ are the numbers of messages, workers, and cache size, respectively. In addition, we study the beneficial cases of content-type coding over large scale networks and over erasure channels. Compared with message-specific coding, we show that the benefits can be up to the number of messages in the content type for the former case and up to $19.5\%$ for the latter case with symmetric setting.