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

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

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

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

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