A Utility-Preserving and Scalable Technique for Protecting Location Data with Geo-Indistinguishability
A Utility-Preserving and Scalable Technique for Protecting Location Data with Geo-Indistinguishability
复制标题
用于保护具有地理不可区分性的位置数据的实用程序保留和可扩展技术
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
C. Shahabi
中科院分区：
文献类型：
--
作者：
Ritesh Ahuja;G. Ghinita;C. Shahabi
基于位置的应用程序为用户提供针对其地理位置的个性化服务。这对于移动的用户来说是非常有益的，他们能够找到靠近他们位置的兴趣点，或者与附近的朋友联系。然而，与服务提供商共享位置数据也引入了隐私问题。能够访问细粒度用户位置的攻击者可以推断出有关个人的隐私细节。GeoInd（GeoInd）采用流行的差分隐私（DP）模型，使其适合保护用户的位置信息。然而，实现GeoInd的现有技术具有主要缺点。一些解决方案，例如平面拉普拉斯机制，通过添加过多的噪声而显著降低数据效用。其他方法，如最优机制，实现了良好的效用，但由于使用计算昂贵的线性规划，仅适用于小的候选位置集。在大多数情况下，位置用于回答在线查询，因此快速响应时间至关重要。在本文中，我们提出了一种实现GeoInd并扩展到大型数据集的技术，同时保留数据实用性。我们的中心思想是使用GeoInd的可组合性属性来创建一个可以与空间索引结合使用的多步算法。我们通过应用精确的GeoInd机制来保持效用，并且在寻求高效用结果时，我们通过在索引的帮助下修剪解决方案搜索空间来实现可扩展性。我们对社交媒体应用程序的真实的位置数据集进行了广泛的性能评估，结果表明，所提出的技术在实用性和/或计算开销方面明显优于基准。
Location-based apps provide users with personalized services tailored to their geographical position. This is highly-beneficial for mobile users, who are able to find points of interest close to their location, or connect with nearby friends. However, sharing location data with service providers also introduces privacy concerns. An adversary with access to fine-grained user locations can infer private details about individuals. Geo-indistinguishability (GeoInd) adapts the popular differential privacy (DP) model to make it suitable for protecting users’ location information. However, existing techniques that implement GeoInd have major drawbacks. Some solutions, such as the planar Laplace mechanism, significantly lower data utility by adding excessive noise. Other approaches, such as the optimal mechanism, achieve good utility, but only work for small sets of candidate locations due to the use of computationally-expensive linear programming. In most cases, locations are used to answer online queries, so a quick response time is essential. In this paper, we propose a technique that achieves GeoInd and scales to large datasets while preserving data utility. Our central idea is to use the composability property of GeoInd to create a multiple-step algorithm that can be used in conjunction with a spatial index. We preserve utility by applying accurate GeoInd mechanisms and we achieve scalability by pruning the solution search space with the help of the index when seeking high-utility outcomes. Our extensive performance evaluation on top of real location datasets from social media apps shows that the proposed technique outperforms significantly the benchmark in terms of utility and/or computational overhead.