The Capacity of Private Information Retrieval From Heterogeneous Uncoded Caching Databases
The Capacity of Private Information Retrieval From Heterogeneous Uncoded Caching Databases
复制标题
DOI：
10.1109/tit.2020.2964762
复制
发表时间：
2019-02
影响因子：
2.5
通讯作者：
Karim A. Banawan;Batuhan Arasli;Yi-Peng Wei;S. Ulukus
中科院分区：
文献类型：
--
作者：
Karim A. Banawan;Batuhan Arasli;Yi-Peng Wei;S. Ulukus
我们考虑从N个非共谋数据库中获取K个文件中的单个文件的私有信息检索(PIR)，这些文件具有异类存储约束${{m}}=({m}_{1}，\cdots，{m}_{{N}})$。该工作的目的是联合设计内容放置阶段和信息检索阶段，以最小化PIR阶段的下载成本。我们将最优PIR下载成本刻画为一个线性规划。通过分析这个线性规划的最优解的结构，我们发现，令人惊讶的是，在我们的异质情况下，最优下载成本与其同质情况下的最优下载成本相匹配，其中所有数据库具有相同的平均存储约束$\MU=\FRAC{1}{{N}}\sum_{{n}=1}^{N}{m}_{{n}}$。因此，我们表明，不会由于数据库存储空间的异构性而损失PIR容量。我们明确地给出了N=3时的最优内容放置。
We consider private information retrieval (PIR) of a single file out of K files from N non-colluding databases with heterogeneous storage constraints ${{m}}=({m}_{1}, \cdots,{m}_{{N}})$ . The aim of this work is to jointly design the content placement phase and the information retrieval phase in order to minimize the download cost in the PIR phase. We characterize the optimal PIR download cost as a linear program. By analyzing the structure of the optimal solution of this linear program, we show that, surprisingly, the optimal download cost in our heterogeneous case matches its homogeneous counterpart where all databases have the same average storage constraint $\mu =\frac {1}{{N}} \sum _{{n}=1}^{N} {m}_{{n}}$ . Thus, we show that there is no loss in the PIR capacity due to heterogeneity of storage spaces of the databases. We provide the optimum content placement explicitly for N = 3.