Caching of Bivariate Gaussians with Non-Uniform Preference Probabilities

Caching is technique that alleviates networks during peak hours by transmitting partial information before a request for any is made. We study this method in a lossy source coding setting with Gaussian databases. A good caching strategy minimizes the data still needed on average once the user requests a file. We identify two important parameters: the prior preference for a file and the correlation among files. This paper characterizes the trade-off between cache and average update communication rate to meet a user's demand using Gaussian codebooks. It is argued that what information needs to be cached not only depends on preference and correlation, but also on the size of the cache.

Function Computation over Networks

Chien-Yi Wang

This thesis looks at efficient information processing for two network applications: content delivery with caching and collecting summary statistics in wireless sensor networks. Both applications are studied under the same paradigm: function computation over networks, where distributed source nodes cooperatively communicate some functions of individual observations to one or multiple destinations. One approach that always works is to convey all observations and then let the destinations compute the desired functions by themselves. However, if the available communication resources are limited, then revealing less unwanted information becomes critical. Centered on this goal, this thesis develops new coding schemes using information-theoretic tools. The first part of this thesis focuses on content delivery with caching. Caching is a technique that facilitates reallocation of communication resources in order to avoid network congestion during peak-traffic times. An information-theoretic model, termed sequential coding for computing, is proposed to analyze the potential gains offered by the caching technique. For the single-user case, the proposed framework succeeds in verifying the optimality of some simple caching strategies and in providing guidance towards optimal caching strategies. For the two-user case, five representative subproblems are considered, which draw connections with classic source coding problems including the Gray-Wyner system, successive refinement, and the Kaspi/Heegard-Berger problem. Afterwards, the problem of distributed computing with successive refinement is considered. It is shown that if full data recovery is required in the second stage of successive refinement, then any information acquired in the first stage will be useful later in the second stage. The second part of this thesis looks at the collection of summary statistics in wireless sensor networks. Summary statistics include arithmetic mean, median, standard deviation, etc, and they belong to the class of symmetric functions. This thesis develops arithmetic computation coding in order to efficiently perform in-network computation for weighted arithmetic sums and symmetric functions. The developed arithmetic computation coding increases the achievable computation rate from

\Theta((\log L)/L)

\Theta(1/\log L)

, where

L

is the number of sensors. Finally, this thesis demonstrates that interaction among sensors is beneficial for computation of type-threshold functions, e.g., the maximum and the indicator function, and that a non-vanishing computation rate is achievable.

EPFL2015

A Gaussian Source Coding Perspective on Caching and Total Correlation

Communication technology has advanced up to a point where children are getting unfamiliar with themost iconic symbol in IT: the loading icon. We no longer wait for something to come on TV, nor for a download to complete. All the content we desire is available in instantaneous and personalized streams. Whereas users benefit tremendously from the increased freedom, the network suffers. Not only do personalized data streams increase the load overall, the instantaneous aspect concentrates traffic around peak hours. The heaviest (mostly video) applications are used predominantly during the evening hours. Caching is a tool to balance traffic without compromising the ‘on-demand’ aspect of content delivery; by sending data in advance a server can avoid peak traffic. The challenge is, of course, that in advance the server has no clue what data the user might be interested in. We study this problem in a lossy source coding setting with Gaussian sources specifically, using amodel based on the Gray–Wyner network. Ultimately caching is a trade-off between anticipating the precise demand through user habits versus ‘more bang for buck’ by exploiting correlation among the files in the database. For two Gaussian sources and using Gaussian codebooks we derive this trade-off completely. Particularly interesting is the case when the user has no preference for some content a-priori, caching then becomes an application of the concepts ofWyner’s common information and Watanabe’s total correlation. We study these concepts in databases of more than two sources where we derive that caching all of the information shared by multiple Gaussians is easy, whereas caching some is hard. We characterize the former, provide an inner bound for the latter and conjecture for which class of Gaussians it is tight. Later we also study how to most efficiently capture the total correlation that exists between two sets of Gaussians. As a final chapter, we study the applicability of caching of discrete information sources by actually building such algorithms, using convolutional codes to ‘cache and compress’. We provide a proof of concept of the practicality for doubly symmetric and circularly symmetric binary sources. Lastly we provide a discussion on challenges to be overcome for generalizing such algorithms.

EPFL2017

Caching (Bivariate) Gaussians

Michael Christoph Gastpar, Guillaume Jean Op 't Veld

Caching is a technique that alleviates networks during peak hours by transmitting partial information before a request for any is made. In a lossy setting of Gaussian databases, we study a single-user model in which good caching strategies minimize the data still needed on average once the user requests a file. The encoder decides on a caching strategy by weighing the benefit from two key parameters: the prior preference for a file and the correlation among the files. Considering uniform prior preference but correlated files, caching becomes an application of Wyner's common information and Watanabe's total correlation. We show this case triggers a split: caching Gaussian sources is a non-convex optimization problem unless one spends enough rate to cache all the common information between files. Combining both correlation and user preference we explicitly characterize the full trade-off when the encoder uses Gaussian codebooks in a database of two files: we show that as the size of the cache increases, the encoder should change strategy and increasingly prioritize user preference over correlation. In this specific case we also address the loss in performance incurred if the encoder has no knowledge of the user's preference and show that this loss is bounded.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020