隐私保护路网查询：基于Voronoi-R*的k近邻方法

"基于Voronoi-R*的隐私保护路网k近邻查询方法" 本文主要探讨了在保护用户位置隐私的前提下，如何高效地执行路网中的k近邻查询。现有的解决方案通常依赖于可信的匿名服务器，这可能导致安全隐患，同时，服务器端的全局路网索引效率不高。为了解决这些问题，作者提出了一个新的基于路网局部索引的隐私保护k近邻查询方法。 该方法首先由查询客户端与位置服务（LBS）服务器进行一轮通信，获取与查询位置相关的局部路网信息。客户端随后生成一个匿名查询序列，该序列包含查询位置所在路段，并确保满足l-路段多样性，以增加查询的混淆度，保护用户的实际位置。这样，客户端无需依赖可信第三方服务器即可提交查询，降低了信任风险。 在LBS服务器端，文章提出了一个分段式的近邻查询处理策略。对于频繁请求的路网区域，服务器构建了一个结合了路网泰森多边形（Voronoi Diagram）和R*树的局部Vor-R*索引结构。这种索引结构可以快速响应查询，减少查找时间。对于不常请求的区域，服务器则采用传统的路网扩张查询处理方式。这种方式降低了索引存储需求，减少了全局索引的访问成本，同时保持了查询结果的准确性，提升了查询处理效率。 此外，文章进行了理论分析和实验验证，证明了提出的Voronoi-R*索引方法在保证查询准确性的前提下，显著提高了处理k近邻查询的效率。该方法尤其适用于大规模路网环境，对于保护位置隐私和提升LBS服务质量具有重要意义。 关键词：路网、位置隐私保护、k近邻查询、Voronoi-R*索引 分类号：TP309 引用格式：倪巍伟，李灵奇，刘家强.基于Voronoi-R*的隐私保护路网k近邻查询方法.软件学报,2019,30(12):3782−3797. 英文引用：Ni WW, Li LQ, Liu JQ. Voronoi-R*-based privacy-preserving k nearest neighbor query over road network. Journal of Software, 2019, 30(12):3782−3797. [doi:10.13328/j.cnki.jos.005583]