障碍空间中基于Voronoi图的组反k最近邻查询研究

发布时间：2018-03-16 16:52

  本文选题：Voronoi图　切入点：组反k最近邻　出处：《计算机研究与发展》2017年04期 　论文类型：期刊论文

【摘要】：为了解决已有研究成果无法有效处理障碍空间中的组反k最近邻查询问题,提出了障碍物环境中基于Voronoi图的OGRkNN查询方法,该方法获得的结果集是将一组查询点中任意一点作为障碍kNN的数据点集合,在实际应用中可以用来评估一组查询对象的影响力.依据障碍物集合是否发生变化提出了2种情况下的OGRkNN查询方法,一种是静态障碍物环境下的OGRkNN查询(简称STA_OGRkNN查询)方法,另一种是动态障碍物环境下的OGRkNN查询(简称DYN_OGRkNN查询)方法.其中STA_OGRkNN查询方法利用Voronoi图的邻接特性可以在剪枝阶段有效地过滤掉大量的非候选者,快速地缩小查询范围,提高整个算法的查询效率,在精炼阶段有效地提高了算法的准确性.进一步给出了3种情况下的DYN_OGRkNN查询方法,分别为障碍物动态增加情况下的OGRkNN查询算法、障碍物动态减少情况下的OGRkNN查询算法以及障碍物动态移动情况下的OGRkNN查询算法.理论研究和实验结果表明所提算法具有较高效率.
[Abstract]:In order to solve the problem of group inverse k-nearest neighbor query in obstacle space, a OGRkNN query method based on Voronoi graph in obstacle environment is proposed. The result set obtained by this method is that any point in a set of query points is taken as the set of data points of the obstacle kNN. In practical application, it can be used to evaluate the influence of a group of query objects. According to the change of obstacle set, this paper proposes two OGRkNN query methods, one is OGRkNN query under static obstacle environment (STA_OGRkNN query), and the other is STA_OGRkNN query. The other is OGRkNN query (DYN_OGRkNN query) method in dynamic obstacle environment, in which STA_OGRkNN query method can filter out a large number of non-candidates effectively in pruning stage by using the adjacency property of Voronoi graph, and reduce the query range quickly. The query efficiency of the whole algorithm is improved, and the accuracy of the algorithm is improved effectively in the refining stage. Furthermore, three DYN_OGRkNN query methods are given in this paper, which are the OGRkNN query algorithm under the condition of dynamic increase of obstacles. The OGRkNN query algorithm in the case of dynamic reduction of obstacles and the OGRkNN query algorithm in the case of dynamic movement of obstacles. The theoretical research and experimental results show that the proposed algorithm has a high efficiency.
【作者单位】： 哈尔滨理工大学计算机科学与技术学院;哈尔滨工业大学计算机科学与技术学院;
【基金】：国家自然科学基金项目(61370084) 黑龙江省自然科学基金项目(F201302) 黑龙江省教育厅科学技术研究项目(12531z004)~~
【分类号】：TP311.13

【相似文献】

相关期刊论文 前10条

1 张桂榕;;反向最近邻查询研究综述[J];电脑知识与技术;2011年28期

2 周屹;;不确定对象的反向最近邻查询研究[J];黑龙江工程学院学报(自然科学版);2012年04期

3 刘永山,薄树奎,张强,郝忠孝;多对象的最近邻查询[J];计算机工程;2004年11期

4 郝忠孝;刘永山;;空间对象的反最近邻查询[J];计算机科学;2005年11期

5 王淼;郝忠孝;;不确定性对象的反向最近邻查询[J];计算机工程;2010年10期

6 张旭;何向南;金澈清;周傲英;;面向不确定图的k最近邻查询[J];计算机研究与发展;2011年10期

7 杨泽雪;郝忠孝;;空间数据库中的障碍反向最近邻查询[J];计算机工程与应用;2011年34期

8 王丹丹;郝忠孝;;道路网络中的多类型K最近邻查询[J];计算机工程与应用;2012年03期

9 邓瑾;周梅;;基于R树及其变种的最近邻查询研究[J];现代计算机;2013年09期

10 朱婧;;平面中点对一般多边形的最近邻查询研究[J];科技通报;2014年01期

相关会议论文 前10条

1 张晓峰;王丽珍;肖清;赵丽红;;基于概念划分的连续最近邻查询研究[A];NDBC2010第27届中国数据库学术会议论文集(B辑)[C];2010年

2 管猛;张剡;柏文阳;;基于地表的连续可见最近邻查询方法[A];NDBC2010第27届中国数据库学术会议论文集(B辑)[C];2010年

3 陈璐;高云君;柳晴;陈刚;;受限相互最近邻查询处理[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

4 盛梅红;沙朝锋;宫学庆;嵇晓;周傲英;;道路网络环境中的多对象最近邻查询[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

5 刘月清;章勇;;一种改进的动态最近邻聚类算法[A];全国自动化新技术学术交流会会议论文集（一）[C];2005年

6 李传文;谷峪;李芳芳;于戈;;一种障碍空间中不确定对象的连续最近邻查询方法[A];NDBC2010第27届中国数据库学术会议论文集A辑一[C];2010年

7 刘星毅;;基于欧式距离的最近邻改进算法[A];广西计算机学会2010年学术年会论文集[C];2010年

8 刘先康;梁菁;任杰;蒋光庆;;修正最近邻模糊分类算法在舰船目标识别中的应用[A];全国第4届信号和智能信息处理与应用学术会议论文集[C];2010年

9 刘俊岭;孙焕良;;多维度量空间中发现相互kNN(英文)[A];NDBC2010第27届中国数据库学术会议论文集A辑二[C];2010年

10 余小高;;P2P环境中k最近邻搜索算法研究[A];2009年全国开放式分布与并行计算机学术会议论文集(下册)[C];2009年

相关博士学位论文 前8条

1 魏本昌;基于内容的大规模图像检索技术研究[D];华中科技大学;2015年

2 杨泽雪;空间连接及最近邻变体查询研究[D];哈尔滨理工大学;2014年

3 孙冬璞;时空数据库多类型最近邻查询的研究[D];哈尔滨理工大学;2010年

4 王建峰;基于哈希的最近邻查找[D];中国科学技术大学;2015年

5 张得天;时间依赖路网高效k最近邻查询混搭机制的研究[D];中国科学技术大学;2014年

6 杜钦生;高维空间的K最近邻查询及连接问题研究[D];吉林大学;2015年

7 张军旗;支持最近邻查找的高维空间索引[D];复旦大学;2007年

8 李艳红;路网中移动对象最近邻及反向最近邻查询处理研究[D];华中科技大学;2011年

相关硕士学位论文 前10条

1 杨根茂;基于哈希加速的近似最近邻检索算法研究[D];浙江大学;2015年

2 原s，

本文编号：1620806