Greedy Iterative and Meta-Heuristic Clustering With Coded Caching and Slepian-Wolf Compression for Correlated Content

Abstract

Content caching has emerged as an effective approach to combat the increasing strains on our current network infrastructure. This method is further improved when combining caching with source coding. However, additional complexity is incurred by creating this hybrid method, as the source coding component comes with associated feasibility constraints and decoding costs. This paper presents an approach to balance this complexity with the coding gains by selecting the best-performing subset of files to compress, while the others are left uncoded. This problem is shown to be NP-hard in general and difficult to solve in an iteration-free manner. To this end, two novel approaches are outlined: an iterative-based solution, which uses the features of the entropy function to derive the most suitable files to compress jointly, and a meta-heuristic version, which is based on the Genetic Algorithm. When compared to an exhaustive search, the proposed solutions are found to be sub-optimal but falling above the 90th percentile of all possible solutions on average. Significantly, the iterative method produces results within one percentile of the meta-heuristic approach yet it finds a solution 2.31 times faster. The iterative approach has an additional benefit, in that it is able to predict the relative gains when adding more files to a compression group. It is thus able to terminate prematurely if the estimated gains are less than a chosen threshold.

Keywords

• Slepian-wolf coding
• distributed source coding
• coded caching
• iterative optimisation