solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看144次
The Capacity of Cache Aided Private Information Retrieval. (arXiv:1706.07035v1 [cs.IT])
来源于:arXiv
The problem of cache enabled private information retrieval (PIR) is
considered in which a user wishes to privately retrieve one out of $K$
messages, each of size $L$ bits from $N$ distributed databases. The user has a
local cache of storage $SL$ bits which can be used to store any function of the
$K$ messages. The main contribution of this work is the exact characterization
of the capacity of cache aided PIR as a function of the storage parameter $S$.
In particular, for a given cache storage parameter $S$, the
information-theoretically optimal download cost $D^{*}(S)/L$ (or the inverse of
capacity) is shown to be equal to $(1- \frac{S}{K})\left(1+ \frac{1}{N}+ \ldots
+ \frac{1}{N^{K-1}}\right)$. Special cases of this result correspond to the
settings when $S=0$, for which the optimal download cost was shown by Sun and
Jafar to be $\left(1+ \frac{1}{N}+ \ldots + \frac{1}{N^{K-1}}\right)$, and the
case when $S=K$, i.e., cache size is large enough to store all messages
locally, for which 查看全文>>