聚集最近鄰查詢技術(shù)研究.pdf

1、隨著移動(dòng)設(shè)備的不斷普及,基于空間位置的查詢服務(wù)已經(jīng)逐漸滲入到人們生活的方方面面。無(wú)論是從歐式空間的查詢研究到路網(wǎng)環(huán)境下的查詢研究,還是從靜態(tài)對(duì)象的查詢研究到移動(dòng)對(duì)象的查詢研究,空間數(shù)據(jù)庫(kù)查詢已變得越來(lái)越多樣化和復(fù)雜化。聚集最近鄰(Aggregate Neareast Neighbor,ANN)查詢作為一種基于位置服務(wù)的空間查詢技術(shù),已經(jīng)成為當(dāng)前的一個(gè)研究熱點(diǎn)問(wèn)題。
　　ANN查詢檢索的是到多個(gè)查詢點(diǎn)距離的聚集函數(shù)值最小的目標(biāo)對(duì)象,

2、其查詢結(jié)果依賴于確定的聚集函數(shù)。目前,ANN查詢已經(jīng)存在不少的研究成果,主要包括歐式空間和路網(wǎng)環(huán)境兩個(gè)方面的研究,然而現(xiàn)有的路網(wǎng)環(huán)境下ANN查詢算法存在空間檢索范圍大以及距離計(jì)算冗余多的問(wèn)題。針對(duì)這些不足,本文首先提出了一種基于影響區(qū)域的ANN查詢算法?？紤]到大量查詢位置同時(shí)發(fā)起查詢請(qǐng)求且要求查詢結(jié)果能夠及時(shí)反饋的實(shí)際需求,本文接下來(lái)提出了一種基于影響區(qū)域的快速ANN查詢算法。
　　首先,分析了ANN查詢本身的一些特性,并總結(jié)了網(wǎng)

3、絡(luò)Voronoi圖在網(wǎng)絡(luò)空間中計(jì)算距離的優(yōu)勢(shì),引入了影響區(qū)域的基本概念,并且給出了相應(yīng)的構(gòu)建算法。
　　接著,通過(guò)對(duì)基于Voronoi圖的ANN查詢算法的深入分析,本文給出了一種基于影響區(qū)域的ANN查詢算法。該算法將Voronoi圖和影響區(qū)域相結(jié)合,在縮小查詢空間范圍的同時(shí)也大大減少了距離的計(jì)算。而后,用真實(shí)的數(shù)據(jù)集分別對(duì)sum聚集函數(shù)和max聚集函數(shù)做了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)驗(yàn)證了基于影響區(qū)域的ANN查詢算法比基于Voronoi圖的AN

4、N查詢算法具有更高的效率。
　　最后,針對(duì)大量查詢點(diǎn)數(shù)據(jù)的處理需求,引入了查詢分組和查詢代表點(diǎn)相關(guān)概念,并給出了一種基于影響區(qū)域的快速ANN查詢算法。該算法是以犧牲查詢結(jié)果的準(zhǔn)確率來(lái)達(dá)到提高查詢速度的目的。實(shí)驗(yàn)給出了查詢分組和組內(nèi)包含的查詢點(diǎn)個(gè)數(shù)對(duì)該算法性能的影響。
　　本文針對(duì)現(xiàn)有ANN查詢算法中存在的不足,創(chuàng)新地提出了基于影響區(qū)域的ANN查詢算法,從而能夠獲得較高的查詢效率。另外,又以現(xiàn)實(shí)需求為驅(qū)動(dòng),給出了基于影響區(qū)域的