张啸剑 金凯忠 孟小峰

1(河南财经政法大学计算机与信息工程学院 郑州 450002) 2 (中国人民大学信息学院 北京 100872) (xjzhang82@ruc.edu.cn)

信息时代的飞速发展，空间数据的获取与收集变得尤为容易，例如移动用户位置、GPS位置、家庭住址等数据.通过对空间数据的分析，使得交通监控、位置推荐等应用能够提高自身的服务质量.然而，空间数据蕴含着丰富的个人敏感信息，在提供给第三方应用的同时，个人的敏感信息有可能被泄露.因此，如何在隐私保护的前提下，发布空间数据是当前基于位置服务的主要挑战问题.匿名化[1]与差分隐私[2-4]是常用的隐私保护模型.然而，匿名模型由于对攻击背景知识与攻击模型给出过多特定假设，而不适合真实的位置服务.例如，文献[5]指出在给出150万条匿名后的用户位置数据，在无任何背景假设情况下，随机给出2个时空点，能够甄别出50%用户的敏感位置，随机给出4个时空点，能够甄别出97%用户的敏感位置.不同于传统的匿名化模型，差分隐私模型要求数据库中任何一个用户的存在都不应显著地改变任何查询的结果，从而保证了每个用户加入该数据库不会对其隐私造成危险.

近年来，出现了几种基于差分隐私的网格空间分割方法.UG(uniform grid)[6]是利用网格结构划分二维空间数据的早期代表方法，该方法首先对空间数据进行均匀划分，然后再对每个单元格添加相应的拉普拉斯噪音.虽然UG能够比较合理地设定划分粒度，但却没有考虑单元……