Subexponential and Linear Subpacketization Coded Caching via Projective Geometry

DOI10.1109/TIT.2021.3095471MaRDI QIDQ4958297zbMATH OpenFDO

Authors Hari Hara Suthan Chittoor, Prasad Krishnan, K. V. Sushena Sree, Bhavana Mamillapalli

Publication date 7 September 2021

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

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

zbMATH Keywords

projective geometries over finite fieldscentralized coded caching schemeslow subpacketizationmoderate rate gains

Mathematics Subject Classification ID

Coding theorems (Shannon theory) (94A24) Source coding (94A29)

Abstract: Large gains in the rate of cache-aided broadcast communication are obtained using coded caching, but to obtain this most existing centralized coded caching schemes require that the files at the server be divisible into a large number of parts (this number is called subpacketization). In fact, most schemes require the subpacketization to be growing asymptotically as exponential in $sqrt[leftroot-1uproot1r]K$ for some positive integer $r$ and $K$ being the number of users. On the other extreme, few schemes having subpacketization linear in $K$ are known; however, they require large number of users to exist, or they offer only little gain in the rate. In this work, we propose two new centralized coded caching schemes with low subpacketization and moderate rate gains utilizing projective geometries over finite fields. Both the schemes achieve the same asymptotic subpacketization, which is exponential in $O((logK{)}^2)$ (thus improving on the $sqrt[leftroot-1uproot1r]K$ exponent). The first scheme has a larger cache requirement but has at most a constant rate (with increasing $K$), while the second has small cache requirement but has a larger rate. As a special case of our second scheme, we get a new linear subpacketization scheme, which has a more flexible range of parameters than the existing linear subpacketization schemes. Extending our techniques, we also obtain low subpacketization schemes for other multi-receiver settings such as distributed computing and the cache-aided interference channel. We validate the performance of all our schemes via extensive numerical comparisons. For a special class of symmetric caching schemes with a given subpacketization level, we propose two new information theoretic lower bounds on the optimal rate of coded caching.

Recommendations

• Coded Caching Schemes with Reduced Subpacketization from Linear Block Codes
• Subspace Properties of Network Coding and Their Applications
• An Exponential Lower Bound on the Sub-Packetization of Minimum Storage Regenerating Codes
• Large scale geometric programming: An application in coding theory
• Geometrically uniform \(n\)-shot subspace codes
• Packing and Covering Properties of Subspace Codes for Error Control in Random Linear Network Coding
• An Improved Sub-Packetization Bound for Minimum Storage Regenerating Codes
• Coded Caching With Nonuniform Demands
• Efficient encoding for a class of subspace subcodes
• Improved Lower Bounds for Coded Caching

Cited in

(1)

• Improved hotplug caching schemes using PDAs and t-designs

This page was built for publication: Subexponential and Linear Subpacketization Coded Caching via Projective Geometry

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