Centralized Coded Caching Schemes: A Hypergraph Theoretical Approach

DOI10.1109/TIT.2018.2847679MaRDI QIDQ4682874zbMATH OpenOpenAlexWikidataFDO

Authors Chong Shangguan, Yiwei Zhang, Gennian Ge

Publication date 19 September 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.03989

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Applications of graph theory (05C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Source coding (94A29) Applications of design theory to circuits and networks (94C30)

Abstract: The centralized coded caching scheme is a technique proposed by Maddah-Ali and Niesen as a solution to reduce the network burden in peak times in a wireless system. Later Yan et al. reformulated the problem as designing a corresponding placement delivery array, and proposed two new schemes from this perspective. These schemes above significantly reduce the transmission rate $R$, compared with the uncoded caching scheme. However, to implement the new schemes, each file should be cut into $F$ pieces, where $F$ increases exponentially with the number of users $K$. Such constraint is obviously infeasible in the practical setting, especially when $K$ is large. Thus it is desirable to design caching schemes with constant rate $R$ (independent of $K$) as well as small $F$. In this paper we view the centralized coded caching problem in a hypergraph perspective and show that designing a feasible placement delivery array is equivalent to constructing a linear and (6, 3)-free 3-uniform 3-partite hypergraph. Several new results and constructions arise from our novel point of view. First, by using the famous (6, 3)-theorem in extremal combinatorics, we show that constant rate caching schemes with $F$ growing linearly with $K$ do not exist. Second, we present two infinite classes of centralized coded caching schemes, which include the schemes of Ali-Niesen and Yan et al. as special cases, respectively. Moreover, our constructions show that constant rate caching schemes with $F$ growing sub-exponentially with $K$ do exist.

Recommendations

• Linear Coded Caching Scheme for Centralized Networks
• A Framework of Constructing Placement Delivery Arrays for Centralized Coded Caching
• On the Placement Delivery Array Design for Centralized Coded Caching Scheme
• Coded Caching With Distributed Storage
• Coded Caching Under Arbitrary Popularity Distributions
• Coded Caching With Nonuniform Demands
• scientific article; zbMATH DE number 1445331
• Allocating objects in a network of caches: centralized and decentralized analyses
• Finite-Length Analysis of Caching-Aided Coded Multicasting

Cited in

(4)

• Sparse hypergraphs with applications to coding theory
• Extremal number of graphs from geometric shapes
• On optimal placement delivery arrays
• Improved hotplug caching schemes using PDAs and t-designs

This page was built for publication: Centralized Coded Caching Schemes: A Hypergraph Theoretical Approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4682874)