190-李传文 一种障碍空间中不确定对象的连续最近邻查询方法.pdfVIP

一种障碍空间中不确定对象的连续最近邻查询方法 1,2 1,2 1,2 1,2 李传文 ，谷峪 ，李芳芳 ，于戈 1 (东北大学 信息科学与工程学院计算机软件与理论研究所 辽宁 沈阳 110004 2 (医学影像计算教育部重点实验室(东北大学) 沈阳 110004) 摘 要 近年来，基于位置的服务获得了越来越广泛的关注，其中最近邻查询是最常用的一种查询方式。测量手段的不准确 性以及数据本身的性质导致不确定性在位置数据中普遍存在，这种不确定性会对最近邻查询结果产生影响。空间中障碍物的 存在也给空间数据查询带来了挑战。文中研究存在障碍物的空间中不确定对象连续最近邻查询的处理方法，设计了一种剪枝 策略大幅降低需要计算的不确定对象数目，并进一步提出了障碍空间中不确定对象最近邻查询安全区域的概念及安全区域生 成算法。设计了安全区域的索引存储方法。实验结果表明，所提出方法具有良好的效率和可扩展性。 关键词：最近邻；不确定；障碍空间；基于位置的服务 中图分类号： 文献标识码： 文章编号： A continuous nearest neighbor query method for uncertain data in obstructed spaces LI Chuan-Wen, Gu Yu, LI Fang-Fang, YU Ge (Institute of Computer Software and Theory of Information Science and Engineering Institute, Northeastern University, Shenyang, 110004, China) Abstract In recent years, location-based services(LBS) are getting more and more attention. The nearest neighbor query is the most common query type in the LBS area. The uncertainty of data exists commonly due to the inaccuracy of measurement instructions and the data attributes itself. This uncertainty will affect the results of nearest neighbor queries. The existence of obstacles in planes also put challenges to spatial data queries. In this paper, we study the continuous nearest neighbor query by the existence of obstacles and the uncertainty of data. We also design a pruning strategy that greatly reducs the number of objects which need to be calculated. Furthermore, we propose the safe region concept with regard to uncertain data in obstructed spaces and propose an algorithm to generate the safe regions. Design an indexing method for saving safe regions. Experimental results show that the proposed method has good efficiency and scalability. Key words: Nearest nei