Content-Type Coding

Speaker: Linqi Song
Affiliation: Ph.D. Candidate - UCLA

Abstract: Traditionally, we use networks to securely and efficiently convey specific information messages to one or more receivers. However, communication networks today are increasingly used to serve a fundamentally different traffic, that delivers types of content rather than specific messages. For instance, when we want to find photos of an event, we may not care which specific photos we receive – we only care about the type of content, namely, that they are photos of the correct event. Content-type traffic pervades a host of applications today, e.g., search engines, recommender systems, and advertising networks. Research on content-type networks is very popular. Most of the existing work looks at how to classify content into types; what to replicate, where and how to store, and from where to retrieve specific data. In contrast, we investigate a totally different question: are there benefits in designing transmission schemes specifically tailored to content-type traffic?

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(log2(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. We prove that this problem is in general NP-hard and propose polynomial time approximation algorithms to make bandwidth aware recommendations. 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 also show the average performance over random instances. Building upon constrained pliable index coding, we design a hierarchical data shuffling scheme for distributed computing that achieves transmission 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.

Biography: Linqi Song received the B.S. and M.S. degrees in Electrical Engineering from Tsinghua University, China. In 2012, he joined the University of California, Los Angeles. He is currently a Ph.D. candidate in the Department of Electrical Engineering. His research interests include information theory and coding theory, network coding and index coding, communications, machine learning and Big Data.

For more information, contact Prof. Christina Fragouli ()

Date(s) - May 08, 2017
2:00 pm - 4:00 pm

E-IV Tesla Room #53-125
420 Westwood Plaza - 5th Flr., Los Angeles CA 90095