基于區(qū)域覆蓋的移動對象K近鄰查詢算法的研究與實現.pdf

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

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

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

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