基于區(qū)域覆蓋的連續(xù)移動查詢算法的研究與實現(xiàn).pdf

1、基于位置服務(wù)的空間查詢在交通導航、救援服務(wù)以及數(shù)字戰(zhàn)場等諸多領(lǐng)域有著廣泛的應(yīng)用前景。近年來，隨著無線通信和全球定位系統(tǒng)(Global Positioning System，GPS)定位技術(shù)的發(fā)展，移動環(huán)境下的查詢技術(shù)的研究已經(jīng)成為移動數(shù)據(jù)庫領(lǐng)域的熱點。由于移動環(huán)境下的查詢對象和被查詢對象均是不斷變化的，因此移動環(huán)境下的查詢比較復雜，并且研究成果較少。連續(xù)查詢不同于只需計算一次的傳統(tǒng)查詢，它需要在一段時間內(nèi)持續(xù)維護查詢結(jié)果，因此在移動環(huán)境

2、下實現(xiàn)起來更加具有挑戰(zhàn)性。本文主要針對移動環(huán)境下的兩類空間查詢技術(shù)展開研究，分別是連續(xù)范圍查詢和連續(xù)K近鄰查詢。
　　首先，Del-VGQ索引是一個層次索引，由Delaunay三角網(wǎng)和虛擬網(wǎng)格四分樹(VirtualGrid Quadtree，VGQ)構(gòu)成。它具備了VGQ索引的快速定位特點和Delaunay三角網(wǎng)能表達對象的鄰近性質(zhì)，該索引適合做移動查詢，但是該索引不能直接完成連續(xù)移動查詢，因此本文擴展了Del-VGQ索引。通過分析

3、移動環(huán)境下對象的特性，本文在擴展后的Del-VGQ索引的基礎(chǔ)上提出了連續(xù)范圍查詢算法DelVGQRangeQuery并且證明了該算法的準確性。接著本文為了驗證算法的性能進行了仿真實驗。實驗結(jié)果表明基于區(qū)域覆蓋的連續(xù)范圍查詢比用TPR-樹索引下的連續(xù)范圍查詢的cpu時間快了一個數(shù)量級。
　　其次，本文分別在VGQ索引和擴展后的Del-VGQ索引的基礎(chǔ)上提出了兩種連續(xù)K近鄰查詢算法VGQKnnQuery和DelVGQKnnQuery，

4、并且分別給出了兩種算法的正確性證明。接著本文為了驗證算法的性能進行了仿真實驗。實驗結(jié)果表明，VGQKnnQuery的查詢響應(yīng)時間慢于DelVGQKnnQuery的查詢響應(yīng)時間，而更新時間前者較快。這是由兩個索引的結(jié)構(gòu)和查詢算法執(zhí)行的過程決定的。另外，DelVGQKnnQuery對大數(shù)據(jù)量具有很好的適應(yīng)性。
　　最后，本文對路網(wǎng)環(huán)境下的連續(xù)K近鄰查詢進行了研究。上述的連續(xù)K近鄰查詢是用歐式距離作為移動對象間的距離，而路網(wǎng)環(huán)境下的連續(xù)