A Rate-Distortion Approach to Caching
- Wed, Nov 01, 2017
We consider a lossy single-user caching problem with correlated sources – just think of streaming compressed videos! Most users will watch these videos in the evening, leading to network congestion. If you have a player with a cache, though, you can fill this cache with data during times of low network usage, even though you may not know which video the user wants to watch in the evening. In our paper, we characterize the transmission rate required in the evening as a function of the cache size and as a function of the distortion one accepts when watching the videos. We furthermore hint at what should be put in the cache such that it is useful for a variety of videos, and we connect these results to the common-information measures proposed by Wyner, Gacs and Koerner.
The picture shows achievable upper (red) and lower converse (black) bounds on the transmission rate as a function of the cache capacity C for doubly symmetric binary source, with the requirement the video is reconstructed perfectly at the receiver. I(X1;X2) denotes the mutual information between the two videos, while KW(X1,X2) denotes Wyner’s common information.
The paper, which has been accepted for publication in the IEEE Transactions on Information Theory, is available on arXiv 1. If you want a three-minute, easy-to-understand summary of the main idea behind information-theoretic caching, take a look at 2.