優(yōu)化的基于Voronoi圖的移動對象K近鄰查詢算法的研究與實現(xiàn).pdf

1、近年來，隨著無線通信和全球定位系統(tǒng)(Global Positioning System，GPS)定位技術的發(fā)展，移動環(huán)境下的查詢技術研究已經成為移動數(shù)據(jù)庫領域的熱點。而其中的移動對象K近鄰查詢更是查詢技術中的重要研究對象之一。K近鄰查詢的研究已經有很多成果，像基于Bx樹、Bdual樹、TPR樹的查詢等，而其中比較高效的是將voronoi圖運用到K近鄰的查詢，利用voronoi圖的特性，提高了查詢的效率。但該索引在移動對象數(shù)據(jù)量和網格劃分

2、個數(shù)的比值較小時性能較差。因此，本文以該問題作為切入點，進行了深入的研究。
　　首先，Del-VGQ索引由Delaunay三角網和虛擬網格四分樹(Virtual Grid Quadtree，VGQ)構成。它具備了VGQ索引的快速定位特點和Delaunay三角網能表達對象的鄰近性質，適合做K近鄰查詢，但是該索引在Delaunay三角網結點的插入刪除時會遞歸檢查周圍的三角形是否滿足空圓特性，性能較差。因此本文針對Delaunay三角網

3、的這個特點，運用延時刪除策略，對Del-VGQ索引進行擴展，提出了K近鄰查詢算法OptDelVGQKnnQuery并證明了該算法的正確性。接著本文對索引的性能進行了仿真實驗。實驗結果表明在移動對象數(shù)據(jù)量和網格個數(shù)的比值較小時，新索引的吞吐量是舊索引的三倍。
　　其次，Del-VGQ索引中運用到了四分樹，而四分樹并不具有平衡的特性，在數(shù)據(jù)分布不均勻時，性能下降很大。針對這個特點，本文用具有平衡特性的R樹代替四分樹，提出了DelRtr

4、eeKnnQuery算法，接著本文對索引性能進行了仿真實驗。實驗結果表明在移動對象數(shù)據(jù)量和網格個數(shù)的比值較小時，新索引的吞吐量是舊索引的兩倍。
　　最后，Del-VGQ索引中網格劃分是固定劃分，這使得數(shù)據(jù)分布不均勻時，不同網格移動對象數(shù)量相差巨大，嚴重影響了索引更新和查詢的效率。針對這個特點，本文設計了均勻密度模型，此時網格劃分不固定，只有當網格內移動對象個數(shù)超過某個閾值才會劃分，盡量使每個網格內的移動對象數(shù)量相同，提高了索引更新