DIKUL - logo
E-viri
Recenzirano Odprti dostop
  • Fundamental Limits of Cache...
    Wei, Yi-Peng; Banawan, Karim; Ulukus, Sennur

    IEEE transactions on information theory, 05/2019, Letnik: 65, Številka: 5
    Journal Article

    We consider the problem of private information retrieval (PIR) from <inline-formula> <tex-math notation="LaTeX">N </tex-math></inline-formula> non-colluding and replicated databases when the user is equipped with a cache that holds an uncoded fraction <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula> from each of the <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula> stored messages in the databases. We assume that the databases are unaware of the cache content. We investigate <inline-formula> <tex-math notation="LaTeX">D^{*}(r) </tex-math></inline-formula> the optimal download cost normalized with the message size as a function of <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">N </tex-math></inline-formula>, and <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula>. For a fixed <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">N </tex-math></inline-formula>, we develop an inner bound (converse bound) for the <inline-formula> <tex-math notation="LaTeX">D^{*}(r) </tex-math></inline-formula> curve. The inner bound is a piece-wise linear function in <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula> that consists of <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula> line segments. For the achievability, we develop explicit schemes that exploit the cached bits as side information to achieve <inline-formula> <tex-math notation="LaTeX">K-1 </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula> that consists of <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">K=3 </tex-math></inline-formula>. For general <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">N </tex-math></inline-formula>, and <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula>, 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.