Full Characterization of Optimal Uncoded Placement for the Structured Clique Cover Delivery of Nonuniform Demands

We investigate the problem of coded caching for nonuniform demands when the structured clique cover algorithm proposed by Maddah-Ali and Niesen for decentralized caching is used for delivery. We apply this algorithm to all user demands regardless of their request probabilities. This allows for codin...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2020-01, Vol.66 (1), p.633-648
Main Authors: Saberali, Seyed Ali, Lampe, Lutz, Blake, Ian F.
Format: Article
Language:English
Subjects:
Algorithms
Caching
Coded caching
convex optimization
Encoding
Libraries
Mathematical analysis
Memory management
Minimization
nonuniform demands
Placement
Polynomials
Resource management
Servers
Storage capacity
Strategy
submodular functions
Terminology
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We investigate the problem of coded caching for nonuniform demands when the structured clique cover algorithm proposed by Maddah-Ali and Niesen for decentralized caching is used for delivery. We apply this algorithm to all user demands regardless of their request probabilities. This allows for coding among the files that have different request probabilities but makes the allocation of memory to different files challenging during the content placement phase. As our main contribution, we analytically characterize the optimal placement strategy that minimizes the expected delivery rate under a storage capacity constraint. It is shown that the optimal placement follows either a two or a three group strategy, where a set of less popular files are not cached at all and the files within each of the other sets are allocated identical amounts of storage as if they had the same request probabilities. We show that for a finite set of storage capacities, that we call the base-cases of the problem, the two group strategy is always optimal. For other storage capacities, optimal placement is achieved by memory sharing between certain base-cases and the resulting placement either follows a two or a three group strategy depending on the corresponding base-cases used. We derive a polynomial time algorithm that determines the base-cases of the problem given the number of caches and popularity distribution of files. Given the base-cases of the problem, the optimal memory allocation parameters for any storage capacity are derived analytically.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2019.2946361