检索结果-内蒙古大学图书馆

IEEE International Symposium on Information Theory (ISIT)

作者： Kumar, Vijith K. P. Rai, Brijesh Kumar Jacob, Tony IIT Guwahati Dept EEE Gauhati India

ISBN: (纸本)9781538682098

The problem of coded caching was introduced by Maddah-Ali and Niesen and has been extensively studied in recent years. The problem is fundamentally a multi-objective optimization problem where the rates achieved for each demand type is of interest and Pareto optimality is a natural framework. Under the constraint that the placement phase is uncoded, Yu et al. introduced the YMA scheme which was shown to be universal for all demand types. Vijith et al. showed that there are no universal schemes when coded placement is permitted and introduced the problem of finding Pareto optimal schemes. In this paper we study the possibility of finding schemes that dominate the YMA scheme and demonstrate, rather surprisingly, that they continue to operate at the Pareto optimal frontier of coded caching for (N, K) cache networks when K <= 3. We introduce new lower bounds which partially characterize the tradeoffs between different demand types.

关键词： Cache network coded caching uncoded prefetching Pareto optimal

来源：评论

学校读者我要写书评

暂无评论

Fundamental Limits of Cache-Aided Private Information Retrieval With Unknown and uncoded prefetching

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2019年第5期65卷 3215-3232页

作者： Wei, Yi-Peng Banawan, Karim Ulukus, Sennur Univ Maryland Dept Elect & Comp Engn College Pk MD 20742 USA

We consider the problem of private information retrieval (PIR) from N non-colluding and replicated databases when the user is equipped with a cache that holds an uncoded fraction r from each of the K stored messages in the databases. We assume that the databases are unaware of the cache content. We investigate D* (r) the optimal download cost normalized with the message size as a function of K, N, and r. For a fixed K and N, we develop an inner bound (converse bound) for the D* (r) curve. The inner bound is a piece-wise linear function in r that consists of K line segments. For the achievability, we develop explicit schemes that exploit the cached bits as side information to achieve K - 1 non-degenerate corner points. These corner points differ in the number of cached bits that are used to generate the one-side information equation. We obtain an outer bound (achievability) for any caching ratio by memory sharing between these corner points. Thus, the outer bound is also a piece-wise linear function in r that consists of K line segments. The inner and the outer bounds match in general for the cases of very low-caching ratio and very high-caching ratio. As a corollary, we fully characterize the optimal download cost caching ratio tradeoff for K = 3. For general K, N, and r, we show that the largest gap between the achievability and the converse bounds is 1/6. Our results show that the download cost can be reduced beyond memory sharing if the databases are unaware of the cached content.

关键词： Private information retrieval caching uncoded prefetching PIR capacity side information

来源：评论

学校读者我要写书评

暂无评论

Cache-Aided Private Information Retrieval With Partially Known uncoded prefetching: Fundamental Limits

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2018年第6期36卷 1126-1139页

作者： Wei, Yi-Peng Banawan, Karim Ulukus, Sennur Univ Maryland Dept Elect & Comp Engn College Pk MD 20742 USA

We consider the problem of private information retrieval from N non-colluding and replicated databases, when the user is equipped with a cache that holds an uncoded fraction r of the symbols from each of the K stored messages in the databases. This model operates in a two-phase scheme, namely, the prefetching phase where the user acquires side information and the retrieval phase where the user privately downloads the desired message. In the prefetching phase, the user receives r/N uncoded fraction of each message from the nth database. This side information is known only to the nth database and unknown to the remaining databases, i.e., the user possesses partially known side information. We investigate the optimal normalized download cost D* (r) in the retrieval phase as a function of K, N, and r. We develop lower and upper bounds for the optimal download cost. The bounds match in general for the cases of very low caching ratio and very high caching ratio. We fully characterize the optimal download cost caching ratio tradeoff for K = 3. For general K, N, and r values, we show that the largest additive gap between the achievability and the converse bounds is 5/32.

关键词： Private information retrieval caching side information distributed databases uncoded prefetching

来源：评论

学校读者我要写书评

暂无评论

Fundamental Limits of Caching: Symmetry Structure and Coded Placement Schemes

Fundamental Limits of Caching: Symmetry Structure and Coded ...

引用

作者： Zhang, Kai Texas A&M University

学位级别：Ph.D., Doctor of Philosophy

Caching is a technique to reduce the communication load in peak hours by prefetching contents during off-peak hours. In 2014, Maddah-Ali and Niesen introduced a framework for coded caching, and showed that significant improvement can be obtained compared to uncoded caching. Considerable efforts have been devoted to identify the precise information theoretic fundamental limit of such systems, however the difficulty of this task has also become clear. One of the reasons for this difficulty is that the original coded caching setting allows multiple demand types during delivery, which in fact introduces tension in the coding strategy to accommodate all of them. We seek to develop a better understanding of the fundamental limit of coded caching. In order to characterize the fundamental limit of the tradeoff between the amount of cache memory and the delivery transmission rate of multiuser caching systems, various coding schemes have been proposed in the literature. These schemes can largely be categorized into two classes, namely uncoded prefetching schemes and coded prefetching schemes. While uncoded prefetching schemes in general over order-wise optimal performance, coded prefetching schemes often have better performance at the low cache memory regime. At first sight it seems impossible to connect these two different types of coding schemes, yet finding a unified coding scheme that achieves the optimal memory-rate tradeoff is an important and interesting problem. We take the first step on this direction and provide a connection between the uncoded prefetching scheme proposed by Maddah Ali and Niesen (and its improved version by Yu et al.) and the coded prefetching scheme proposed by Tian and Chen. The intermediate operating points of this general scheme can in fact provide new memory-rate tradeoff points previously not known to be achievable in the literature. This new general coding scheme is then presented and analyzed rigorously, which yields a new inner bound to th

关键词： Caching network Linear Programming Symmetry structure Coding scheme Fundamental limit uncoded prefetching

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：