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

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

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

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

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