施洪洁

【摘要】LBS匿名模型中的关键问题在于如何寻找满足匿名条件的匿名空间，匿名空间越大，空间内用户数越多，攻者能判断出目标用户的概率越小，即匿名度越好，但是同时，增大的匿名空间也增大了用户位置精确度的损失，服务器返回的候选结果集与用户的真实请求结果之间的差距越大，即服务质量就越差，反之，较小的匿名空间服务质量增强，而匿名度较弱。因此，匿名空间查找方法的原则是在匿名度和服务质量之间需找一个最佳的平衡点，本文首先指出了目前最典型的匿名空间查找算法过程中产生的大量的空间冗余现象是因为空间划分精度太粗，而且没有考虑用户分布情况，因此，本文引入网格和密度的概念，提出了基于网格和密度的匿名空间查找算法。

【关键词】位置服务 查询隐私 k-匿名 网格和密度 最小匿名空间

【中图分类号】TP309 【文献标识码】A 【文章编号】2095-3089（2016）11-0249-01

Interval Cloak产生的大量的空间冗余现象是由于空间划分精度太粗和没有考虑用户分布情况，体现用户分布不均匀的状态就是密度的概念，而空间网格化是为了提高空间划分的精度。本节将在地理信息系统中应用比较成熟的网格技术，对空间进行网格划分，以网格为一个计算单元，再根据用户分布密度，在用户分布相对密度最大的范围内寻找合适的匿名集。

一、算法原理

在地理信息系统中，网格数据模型被用来分析空间特征，由于其数据结构简单，且成本低廉等优势，在地理空间分析中得到了广泛应用。……