We consider the problem of private information retrieval from $N$ emph{storage-constrained} databases. In this problem, a user wishes to retrieve a single message out of $M$ messages (of size $L$) without revealing any information about the identity of the message to individual databases. Each database stores $mu ML$ symbols, i.e., a $mu$ fraction of the entire library, where $frac{1}{N} leq mu leq 1$. Our goal is to characterize the optimal tradeoff curve for the storage cost (captured by $mu$) and the normalized download cost ($D/L$). We show that the download cost can be reduced by employing a hybrid storage scheme that combines emph{MDS coding} ideas with emph{uncoded partial replication} ideas. When there is no coding, our scheme reduces to Attia-Kumar-Tandon storage scheme, which was initially introduced by Maddah-Ali-Niesen in the context of the caching problem, and when there is no uncoded partial replication, our scheme reduces to Banawan-Ulukus storage scheme; in general, our scheme outperforms both.
Download