一、摘要
主要研究问题基于本地化差分隐私的k-分布，之前最佳的算法要求的是线性通信代价(k)，而服务器计算时间的n*k，n表示所有的用户样本。
作者提出的HR不要求共享随机性，并且每个用户输入的数据都是对称的，对于所有的隐私预算ε ，每个用户的通信代价为logk+2，服务器计算时间为O(n+k)。
文中的编码和解码主要基于哈达玛矩阵，统计性能包括行之间的最大汉明距离，算法高效实现使用了Fast Walsh-Hadamard变换，从而获得计算增益。
二、引言
1、效用值
我们即希望保护用户的个人隐私，又能够得到多个用户样本的估计分布。
2、隐私
之前的隐私分布估计没有考虑到两个重要的资源，用户的通信复杂度和客户端的计算复杂度，特别是在用户数据较多时，计算代价就会很高。
3、计算复杂度
heavy hitters中要求共享随机性并且是非对称方案，[7]使用哈达玛变换，与本文不同的是用于形成正交基础和减少存储。
4、通信复杂度
每个用户发送到服务端的位数，之前是k位，本文实现了对数通信。
三、初始化