基于區(qū)域覆蓋的移動(dòng)對(duì)象K近鄰查詢算法的研究與實(shí)現(xiàn).pdf

1、近年來(lái)，隨著科技的發(fā)展，與位置服務(wù)有關(guān)的定位技術(shù)、導(dǎo)航技術(shù)、監(jiān)控技術(shù)已經(jīng)廣泛走進(jìn)現(xiàn)實(shí)生活。如今，手機(jī)、車載設(shè)備等電子產(chǎn)品提供位置服務(wù)相關(guān)功能越來(lái)越普遍。這些應(yīng)用的技術(shù)基礎(chǔ)空間數(shù)據(jù)庫(kù)的研究也越來(lái)越成為熱點(diǎn)問題之一。其中移動(dòng)對(duì)象的K近鄰查詢就是空間數(shù)據(jù)庫(kù)中重要的應(yīng)用之一。例如，在交通管理中，一輛出租車要查找當(dāng)前時(shí)刻距它最近的前K個(gè)旅館或加油站，使出租車司機(jī)可以選擇一個(gè)離自己不遠(yuǎn)又順路的結(jié)果;在戰(zhàn)爭(zhēng)中，一個(gè)戰(zhàn)士要查找自己附近的人員的位置情況;

2、在航海中，一艘輪船要查詢距離自己較近的若干艘輪船等。盡管K近鄰查詢的研究工作已有很多成果，但對(duì)在大量移動(dòng)對(duì)象頻繁移動(dòng)的環(huán)境下，現(xiàn)有索引在高效更新，快速近鄰查詢方面表現(xiàn)不是很理想。因此，本文從該問題作為切入點(diǎn)，進(jìn)行了深入研究。
　　首先，本文通過分析移動(dòng)對(duì)象在頻繁移動(dòng)情況下進(jìn)行k近鄰查詢的難點(diǎn)——查詢與更新的特性，利用網(wǎng)格文件解決頻繁更新的問題，利用Voronoi圖解決近鄰查詢的問題，提出了一種基于區(qū)域覆蓋的虛擬網(wǎng)格四分樹(Virt

3、ual Grid Quadtree，VGQ)與VoronoiDiagram相結(jié)合(Vor-VGQ)的索引結(jié)構(gòu)。結(jié)合兩種結(jié)構(gòu)的優(yōu)點(diǎn)，該索引適合近鄰查詢并且支持動(dòng)態(tài)更新。它通過索引移動(dòng)對(duì)象所在區(qū)域而非移動(dòng)對(duì)象本身來(lái)減少由于移動(dòng)對(duì)象位置改變而引起的索引結(jié)構(gòu)的更新。
　　其次，在Vor-VGQ索引結(jié)構(gòu)基礎(chǔ)上做了2種策略的K近鄰處理方法。一種面向于提高查詢效率的實(shí)時(shí)動(dòng)態(tài)Voronoi Diagram變換策略，隨著網(wǎng)格的變化Voronoi D

4、iagram同步變化。在試驗(yàn)過程中發(fā)現(xiàn)路網(wǎng)中數(shù)據(jù)分布的相對(duì)穩(wěn)定性，從而提出了面向于提高更新效率的單調(diào)動(dòng)態(tài)Voronoi Diagram更新策略，最終形成依據(jù)路網(wǎng)分布的穩(wěn)定的VoronoiDiagram結(jié)構(gòu)。利用上述兩種策略設(shè)計(jì)了范圍查詢和KNN查詢的算法，并且證明了算法的準(zhǔn)確性。
　　最后，本文設(shè)計(jì)了實(shí)驗(yàn)并進(jìn)行了對(duì)比分析。實(shí)驗(yàn)結(jié)果表明，Vor-VGQ是一種高效的空間數(shù)據(jù)索引結(jié)構(gòu)，基于Vor-VGQ索引結(jié)構(gòu)的KNN查詢與已有B+樹類