We design a scalable algorithm to privately generate location heatmaps over decentralized data from millions of user devices. It aims to ensure differential privacy before data becomes visible to a service provider while maintaining high data accuracy and minimizing resource consumption on users' devices. To achieve this, we revisit distributed differential privacy based on recent results in secure multiparty computation, and we design a scalable and adaptive distributed differential privacy approach for location analytics. Evaluation on public location datasets shows that this approach successfully generates metropolitan-scale heatmaps from millions of user samples with a worst-case client communication overhead that is significantly smaller than existing state-of-the-art private protocols of similar accuracy.
翻译:我们设计了一种可扩缩的算法,对来自数百万用户装置的分散数据私下生成位置热谱图,其目的是在数据为服务提供者所见之前确保有差别的隐私,同时保持高数据准确性并尽量减少用户装置的资源消耗。为了做到这一点,我们根据安全多功能计算的最新结果重新审视分散的隐私,并为地点分析设计一种可扩缩和适应的分散的隐私方法。对公共地点数据集的评估表明,这一方法成功地从数百万用户样本中生成了大都市热谱图,这些样本的客户通信管理费用最差,大大小于现有最先进的类似精确的私人协议。