2015/04/30 by Chien-Yi Wang, Sung Hoon Lim, Michael Gastpar · 46 citations
Computer Science · Engineering · Mathematics · #Algorithm #Caching and Content Delivery #Coding (social sciences) #Computer science #Cooperative Communication and Network Coding #Decoding methods #Distributed computing #Distributed source coding #Information theory #Mathematics #Theoretical computer science #Variable-length code #Wireless Communication Security Techniques #cs.IT #math.IT
paper · pdf · doi:10.1109/tit.2016.2604851
published in IEEE Transactions on Information Theory 62(11), 6393-6406 (Institute of Electrical and Electronics Engineers) · submitted to IEEE Trans. Inf. Theory and presented in part at ISIT 2015
arxiv created 2016/02/27 · openalex publication_date 2016/08/31 · arxiv updated 2016/11/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Under the paradigm of caching, partial data are delivered before the actual requests of users are known. In this paper, this problem is modeled as a canonical distributed source coding problem with side information, where the side information represents the users' requests. For the single-user case, a singleletter characterization of the optimal rate region is established, and for several important special cases, closed-form solutions are given, including the scenario of uniformly distributed user requests. In this case, it is shown that the optimal caching strategy is closely related to total correlation and Wyner's common information. Using the insight gained from the single-user case, three two-user scenarios admitting single-letter characterization are considered, which draw connections to existing source coding problems in the literature: the Gray-Wyner system and distributed successive refinement. Finally, the model studied by Maddah-Ali and Niesen is rephrased to make a comparison with the considered information-theoretic model. Although the two caching models have a similar behavior for the single-user case, it is shown through a two-user example that the two caching models behave differently in general.