本文選題：Voronoi圖　切入點(diǎn)：組反k最近鄰　出處：《計(jì)算機(jī)研究與發(fā)展》2017年04期 　論文類型：期刊論文

【摘要】：為了解決已有研究成果無法有效處理障礙空間中的組反k最近鄰查詢問題,提出了障礙物環(huán)境中基于Voronoi圖的OGRkNN查詢方法,該方法獲得的結(jié)果集是將一組查詢點(diǎn)中任意一點(diǎn)作為障礙kNN的數(shù)據(jù)點(diǎn)集合,在實(shí)際應(yīng)用中可以用來評(píng)估一組查詢對(duì)象的影響力.依據(jù)障礙物集合是否發(fā)生變化提出了2種情況下的OGRkNN查詢方法,一種是靜態(tài)障礙物環(huán)境下的OGRkNN查詢(簡(jiǎn)稱STA_OGRkNN查詢)方法,另一種是動(dòng)態(tài)障礙物環(huán)境下的OGRkNN查詢(簡(jiǎn)稱DYN_OGRkNN查詢)方法.其中STA_OGRkNN查詢方法利用Voronoi圖的鄰接特性可以在剪枝階段有效地過濾掉大量的非候選者,快速地縮小查詢范圍,提高整個(gè)算法的查詢效率,在精煉階段有效地提高了算法的準(zhǔn)確性.進(jìn)一步給出了3種情況下的DYN_OGRkNN查詢方法,分別為障礙物動(dòng)態(tài)增加情況下的OGRkNN查詢算法、障礙物動(dòng)態(tài)減少情況下的OGRkNN查詢算法以及障礙物動(dòng)態(tài)移動(dòng)情況下的OGRkNN查詢算法.理論研究和實(shí)驗(yàn)結(jié)果表明所提算法具有較高效率.
[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.
【作者單位】： 哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;
【基金】：國(guó)家自然科學(xué)基金項(xiàng)目(61370084) 黑龍江省自然科學(xué)基金項(xiàng)目(F201302) 黑龍江省教育廳科學(xué)技術(shù)研究項(xiàng)目(12531z004)~~
【分類號(hào)】：TP311.13

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 張桂榕;;反向最近鄰查詢研究綜述[J];電腦知識(shí)與技術(shù);2011年28期

2 周屹;;不確定對(duì)象的反向最近鄰查詢研究[J];黑龍江工程學(xué)院學(xué)報(bào)(自然科學(xué)版);2012年04期

3 劉永山,薄樹奎,張強(qiáng),郝忠孝;多對(duì)象的最近鄰查詢[J];計(jì)算機(jī)工程;2004年11期

4 郝忠孝;劉永山;;空間對(duì)象的反最近鄰查詢[J];計(jì)算機(jī)科學(xué);2005年11期

5 王淼;郝忠孝;;不確定性對(duì)象的反向最近鄰查詢[J];計(jì)算機(jī)工程;2010年10期

6 張旭;何向南;金澈清;周傲英;;面向不確定圖的k最近鄰查詢[J];計(jì)算機(jī)研究與發(fā)展;2011年10期

7 楊澤雪;郝忠孝;;空間數(shù)據(jù)庫中的障礙反向最近鄰查詢[J];計(jì)算機(jī)工程與應(yīng)用;2011年34期

8 王丹丹;郝忠孝;;道路網(wǎng)絡(luò)中的多類型K最近鄰查詢[J];計(jì)算機(jī)工程與應(yīng)用;2012年03期

9 鄧瑾;周梅;;基于R樹及其變種的最近鄰查詢研究[J];現(xiàn)代計(jì)算機(jī);2013年09期

10 朱婧;;平面中點(diǎn)對(duì)一般多邊形的最近鄰查詢研究[J];科技通報(bào);2014年01期

相關(guān)會(huì)議論文 前10條

1 張曉峰;王麗珍;肖清;趙麗紅;;基于概念劃分的連續(xù)最近鄰查詢研究[A];NDBC2010第27屆中國(guó)數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集(B輯)[C];2010年

2 管猛;張剡;柏文陽;;基于地表的連續(xù)可見最近鄰查詢方法[A];NDBC2010第27屆中國(guó)數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集(B輯)[C];2010年

3 陳璐;高云君;柳晴;陳剛;;受限相互最近鄰查詢處理[A];第29屆中國(guó)數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（B輯）（NDBC2012）[C];2012年

4 盛梅紅;沙朝鋒;宮學(xué)慶;嵇曉;周傲英;;道路網(wǎng)絡(luò)環(huán)境中的多對(duì)象最近鄰查詢[A];第二十三屆中國(guó)數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2006年

5 劉月清;章勇;;一種改進(jìn)的動(dòng)態(tài)最近鄰聚類算法[A];全國(guó)自動(dòng)化新技術(shù)學(xué)術(shù)交流會(huì)會(huì)議論文集（一）[C];2005年

6 李傳文;谷峪;李芳芳;于戈;;一種障礙空間中不確定對(duì)象的連續(xù)最近鄰查詢方法[A];NDBC2010第27屆中國(guó)數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集A輯一[C];2010年

7 劉星毅;;基于歐式距離的最近鄰改進(jìn)算法[A];廣西計(jì)算機(jī)學(xué)會(huì)2010年學(xué)術(shù)年會(huì)論文集[C];2010年

8 劉先康;梁菁;任杰;蔣光慶;;修正最近鄰模糊分類算法在艦船目標(biāo)識(shí)別中的應(yīng)用[A];全國(guó)第4屆信號(hào)和智能信息處理與應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2010年

9 劉俊嶺;孫煥良;;多維度量空間中發(fā)現(xiàn)相互kNN(英文)[A];NDBC2010第27屆中國(guó)數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集A輯二[C];2010年

10 余小高;;P2P環(huán)境中k最近鄰搜索算法研究[A];2009年全國(guó)開放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集(下冊(cè))[C];2009年

相關(guān)博士學(xué)位論文 前8條

1 魏本昌;基于內(nèi)容的大規(guī)模圖像檢索技術(shù)研究[D];華中科技大學(xué);2015年

2 楊澤雪;空間連接及最近鄰變體查詢研究[D];哈爾濱理工大學(xué);2014年

3 孫冬璞;時(shí)空數(shù)據(jù)庫多類型最近鄰查詢的研究[D];哈爾濱理工大學(xué);2010年

4 王建峰;基于哈希的最近鄰查找[D];中國(guó)科學(xué)技術(shù)大學(xué);2015年

5 張得天;時(shí)間依賴路網(wǎng)高效k最近鄰查詢混搭機(jī)制的研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2014年

6 杜欽生;高維空間的K最近鄰查詢及連接問題研究[D];吉林大學(xué);2015年

7 張軍旗;支持最近鄰查找的高維空間索引[D];復(fù)旦大學(xué);2007年

8 李艷紅;路網(wǎng)中移動(dòng)對(duì)象最近鄰及反向最近鄰查詢處理研究[D];華中科技大學(xué);2011年

相關(guān)碩士學(xué)位論文 前10條

1 楊根茂;基于哈希加速的近似最近鄰檢索算法研究[D];浙江大學(xué);2015年

2 原s，

本文編號(hào)：1620806