E-viri
Recenzirano
Odprti dostop
-
Fundamental Limits of Cache-Aided Private Information Retrieval With Unknown and Uncoded PrefetchingWei, Yi-Peng; Banawan, Karim; Ulukus, Sennur
IEEE transactions on information theory, 05/2019, Letnik: 65, Številka: 5Journal 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.
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.