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

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.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.哈尔滨理工大学计算机科学与技术学院，哈尔滨 150080
2.哈尔滨理工大学计算中心，哈尔滨 150080

Abstract

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图, 最近邻查询, 障碍物, 单纯型连续近邻链

ZHANG Liping1, LI Song1, HAO Xiaohong2, HAO Zhongxiao1. Simple continues near neighbor chain query with increase and decrease of obstacles[J]. Computer Engineering and Applications, 2015, 51(11): 99-103.

张丽平1，李松1，郝晓红2，郝忠孝1. 障碍物增减情况下的单纯型连续近邻链查询[J]. 计算机工程与应用, 2015, 51(11): 99-103.

[1]	ZHANG Jun, ZHU Qingwei, YAN Junjie, WEN Bo. UAV Indoor 3D Track Planning Based on Improved Reinforcement Learning Algorithm [J]. Computer Engineering and Applications, 2021, 57(16): 175-181.
[2]	GUO Na, LI Caihong, WANG Di, ZHANG Ning, LIU Guoming. Path Planning of Mobile Robot Based on Prediction and Fuzzy Control [J]. Computer Engineering and Applications, 2020, 56(8): 104-109.
[3]	ZHU Jie1, LU Yi2, ZHANG Huiming1. Path replanning for UAV in emergent threats [J]. Computer Engineering and Applications, 2018, 54(8): 255-259.
[4]	YANG Zexue. Research on hybrid index structure in spatial database [J]. Computer Engineering and Applications, 2017, 53(20): 20-23.
[5]	XIA Chunrui1, WANG Rui1, LI Xiaojuan1, GUAN Yong1, ZHANG Jie2, WEI Hongxing3. Probabilistic model checking for path planning in dynamic environment [J]. Computer Engineering and Applications, 2016, 52(12): 5-11.
[6]	ZHOU Yi1, YANG Zexue1，2. Research on line segment kNN query in spatial database [J]. Computer Engineering and Applications, 2015, 51(18): 131-134.
[7]	XU Ming, CAO Han, TANG Duoyu. Generation and application of weighted Voronoi diagrams for polygons based on Hadoop [J]. Computer Engineering and Applications, 2015, 51(13): 59-62.
[8]	XU Hongbo1，2, YAO Nianmin2, HAN Qilong2, PAN Haiwei2. Index structure CB-tree supporting line query [J]. Computer Engineering and Applications, 2015, 51(11): 114-118.
[9]	YU Jing, CAO Han, JIN Pengfei. Matrix iteration based parallel algorithm of k-order Voronoi diagram [J]. Computer Engineering and Applications, 2014, 50(6): 102-105.
[10]	XIAO Qiuyong, LI Guangqiang. Comparative experimental analysis for capacities of spatial database [J]. Computer Engineering and Applications, 2014, 50(21): 139-142.
[11]	HUA Binjie, LIN Lizhong, CHAI Zhongliang. Research on discrete generation algorithm of Voronoi diagram based rough area [J]. Computer Engineering and Applications, 2013, 49(23): 191-194.
[12]	WU Bo1，2, WEN Yuanqiao1，2, XIAO Changshi1，2. Design and simulation of inland maritime unmanned surface vessel path-planning algorithm [J]. Computer Engineering and Applications, 2013, 49(14): 241-246.
[13]	ZHANG Yibin1, WU Gang1, PENG Wenxiu2, CHEN Yanru3. Generation of Voronoi diagram of different traffic network speed [J]. Computer Engineering and Applications, 2012, 48(36): 181-185.
[14]	HUANG Yonglong, ZHONG Xunyu. Improved velocity obstacles-based collision avoidance algorithm for multiple mobile robots [J]. Computer Engineering and Applications, 2012, 48(32): 47-51.
[15]	LIN Jian, LIU Renyi, LIU Nan, ZHANG Feng. New distributed spatial query optimization approach by using query analyzer [J]. Computer Engineering and Applications, 2012, 48(22): 161-165.

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

障碍物增减情况下的单纯型连续近邻链查询

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics