Abstract: In this paper, the concept of multi-object convergence problem was introduced. While some former query techniques could be used to deal with this problem, they are all point-based and unable to protect location privacy. Hence, a range-based spatial Skyline query algorithm named VRSSA was proposed. It utilized the Voronoi graph and supported the spatial anonymity techniques in Location-based Service (LBS). Furthermore, with respect to the changes of query conditions, another two algorithms, Dynamic Point Joining Algorithm (DPJA) and Dynamic Point Deleting Algorithm (DPDA), to dynamically update the query results were proposed so that heavy re-computation could be avoided. The experimental results show that the approaches could efficiently and effectively solve the problem.

Key words: Location-based Service (LBS), context-aware computing, Skyline queries, range queries, Voronoi graph, privacy protection

摘要： 针对基于位置服务中的多个查询者聚集的场景，提出一种兼顾用户隐私的基于区域的空间Skyline查询算法——VRSSA，利用Voronoi图等计算几何学方法，解决了基于区域与点之间距离的控制关系的判定，并有效减少了计算的复杂度。同时，针对查询条件的动态改变，提出了两种动态更新算法：被查询对象动态新增算法(DPJA)和被查询对象动态减少算法(DPDA)，可有效地减少重复计算的消耗。实验结果证明，提出的算法总体效率较好，具有一定的灵活性。

关键词: 基于位置的服务, 上下文感知计算, Skyline查询, 区域查询, Voronoi图, 隐私保护