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

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

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

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

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