Fetching the paper…

Reading the bibliography…

2017

The Capacity of Cache Aided Private Information Retrieval

Tandon, Ravi

Original
PDF
Post on X

Understand

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)$.

The Capacity of Cache Aided Private Information Retrieval · Around

Built on

Private information retrieval
B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan · 1995
Earlier work this paper cites.
Computationally private information retrieval with polylogarithmic communication
C. Cachin, S. Micali, and M. Stadler · 1999
Earlier work this paper cites.
Private information retrieval
S. Yekhanin · 2010
Earlier work this paper cites.
Elements of information theory
Original
T. M. Cover and J. A. Thomas · 2012
Earlier work this paper cites.
RAID-PIR: Practical multi-server PIR
D. Demmler, A. Herzberg, and T. Schneider · 2014
Earlier work this paper cites.
“one extra bit of download ensures perfectly private information retrieva
N. Shah, K. Rashmi, and K. Ramchandran · 2014
Earlier work this paper cites.

Similar

Scalable and private media consumption with popcorn
T. Gupta, N. Crooks, W. Mulhern, S. Setty, L. Alvisi, and M. Walfish · 2016
Cited alongside, same era.
The capacity of robust private information retrieval with colluding databases
Original
H. Sun and S. A Jafar · 2016
Cited alongside, same era.
Private information retrieval from MDS coded data in distributed storage systems
Original
R. Tajeddine and S. El Rouayheb · 2016
Cited alongside, same era.
The capacity of private information retrieval from coded databases
Original
K. Banawan and S. Ulukus · 2016
Cited alongside, same era.
Private information retrieval from coded databases with colluding servers
Original
R. Freij-Hollanti, O. W. Gnilke, C. Hollanti, and D. A. Karpuk · 2016

Then

Symmetric private information retrieval for MDS coded distributed storage
Original
Q. Wang and M. Skoglund · 2016
Later among the works it cites.
The capacity of private information retrieval
H. Sun and S. A. Jafar · 2017
Closest in time.
The capacity of private information retrieval from byzantine and colluding databases
Original
K. Banawan and S. Ulukus · 2017
Closest in time.
Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al
Original
H. Sun and S. A. Jafar · 2017
Closest in time.
Multi-message private information retrieval: Capacity results and near-optimal schemes
Original
K. Banawan and S. Ulukus · 2017

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Cited alongside, same era.

The capacity of symmetric private information retrieval

H. Sun and S. A. Jafar · 2016

Cited alongside, same era.

Closest in time.

Multi-file private information retrieval from MDS coded databases with colluding servers

Y. Zhang and G. Ge · 2017

Closest in time.