计算机应用 ›› 2011, Vol. 31 ›› Issue (09): 2389-2394.DOI: 10.3724/SP.J.1087.2011.02389

• 数据库技术 • 上一篇    下一篇

基于用户隐私保护的区域多对象聚集问题

谈嵘,顾君忠,林欣,陈鹏   

  1. 华东师范大学 信息科学技术学院,上海 200241
  • 收稿日期:2011-03-24 修回日期:2011-05-22 发布日期:2011-09-01 出版日期:2011-09-01
  • 通讯作者: 谈嵘
  • 作者简介:谈嵘(1984-),男,上海人,博士研究生,主要研究方向:情景感知计算;
    顾君忠(1949-),男,上海人,教授,主要研究方向:协同计算、分布式数据库管理、智能多媒体;
    林欣(1981-),男,福建福州人,讲师,博士,主要研究方向:普适计算;
    陈鹏(1985-),男,山东菏泽人,博士研究生,主要研究方向:数据库管理。
  • 基金资助:
    国家自然科学基金资助项目(61003131;61003138;61073116);上海市国际科技合作基金资助项目(09510703000;10dz1500103)

Range-based approach for multi-object convergence problem

TAN Rong,GU Jun-zhong,LIN Xin,CEHN Peng   

  1. School of Information Science and Technology, East China Normal University, Shanghai 200241, China
  • Received:2011-03-24 Revised:2011-05-22 Online:2011-09-01 Published:2011-09-01
  • Contact: TAN Rong

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

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

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

中图分类号: