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

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

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

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

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