Computer Engineering and Applications ›› 2015, Vol. 51 ›› Issue (11): 99-103.

Previous Articles     Next Articles

Simple continues near neighbor chain query with increase and decrease of obstacles

ZHANG Liping1, LI Song1, HAO Xiaohong2, HAO Zhongxiao1   

  1. 1.School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China
    2.Computation Center , Harbin University of Science and Technology, Harbin 150080, China
  • Online:2015-06-01 Published:2015-06-12


张丽平1,李  松1,郝晓红2,郝忠孝1   

  1. 1.哈尔滨理工大学 计算机科学与技术学院,哈尔滨 150080
    2.哈尔滨理工大学 计算中心,哈尔滨 150080

Abstract: The Simple Continues Near Neighbor Chain Query (SCNNC-Query) has important significance in the spatial data mining, spatial database, similarity analysis and reasoning of data etc. To remedy the deficiency of the existing work, the Simple Continues Near Neighbor Chain Query with dynamic Obstacles (ObSCNNC-Query) is studied. Based on the Voronoi diagram and judging circle, the ObSCNNC_Search algorithm, the ObSCNNC_ADD algorithm and the ObSCNNC_DET algorithm are given. Furthermore, the performance of the methods is analyzed and compared by experiment. The theatrical study and the experimental results show that the algorithms have great advantages.

Key words: spatial database, Voronoi diagram, near neighbor query, obstacles, simple continues near neighbor chain

摘要: 单纯型连续近邻链查询在空间数据挖掘、空间数据库、数据的相似分析和推理等方面具有重要的作用。为了弥补已有方法的不足,对动态障碍物环境下的单纯型连续近邻链查询(ObSCNNC查询)问题进行了详细研究。利用Voronoi图和判定圆给出了ObSCNNC_Search算法,进一步提出了障碍物动态增加情况下的查询算法(ObSCNNC_ADD算法)和障碍物动态减少情况下的查询算法(ObSCNNC_DET算法)。对所提方法进行了实验比较与分析。理论研究与实验分析表明,所提方法较适合处理障碍物环境下的单纯型连续近邻链问题。

关键词: 空间数据库, Voronoi图, 最近邻查询, 障碍物, 单纯型连续近邻链