移動(dòng)對(duì)象及其最近鄰查詢算法研究.pdf

1、移動(dòng)計(jì)算、無線通信以及定位技術(shù)的快速發(fā)展使得對(duì)各種空間與時(shí)空對(duì)象的存儲(chǔ)和管理成為了現(xiàn)實(shí)需求，也使得跟蹤并記錄移動(dòng)對(duì)象的位置成為可能。大量的應(yīng)用領(lǐng)域（如地理信息系統(tǒng)、智能導(dǎo)航、交通管制、天氣預(yù)報(bào)、軍事、移動(dòng)電子商務(wù)等）均迫切需要有效地查詢這些數(shù)據(jù)對(duì)象。因此空間數(shù)據(jù)查詢的問題迅速成為了研究的熱點(diǎn)，其中移動(dòng)對(duì)象的最近鄰查詢作為空間數(shù)據(jù)查詢中最重要的查詢之一，也受到了社會(huì)各個(gè)領(lǐng)域的廣泛關(guān)注。
　　 移動(dòng)對(duì)象的最近鄰查詢算法的查詢效率是衡

2、量其查詢性能的重要指標(biāo)之一，盡管已有許多的研究學(xué)者致力于這方面的研究，并取得了許多可喜的成果，然而，目前的研究大多集中在在如何提高單個(gè)查詢請(qǐng)求的效率，但在實(shí)際應(yīng)用時(shí)，服務(wù)器經(jīng)常會(huì)同時(shí)收到大量的查詢請(qǐng)求，用傳統(tǒng)的最近鄰查詢算法在處理這種情況時(shí)效率就比較低。
　　 鑒于此，本文在對(duì)傳統(tǒng)的移動(dòng)對(duì)象最近鄰查詢算法的分析和研究的基礎(chǔ)上，提出了一種基于對(duì)查詢點(diǎn)聚類的最近鄰查詢算法。本文的主要貢獻(xiàn)可歸納為：
　　 1．對(duì)Jensen模

3、型進(jìn)行了擴(kuò)充和完善，并給出了完整的路網(wǎng)和對(duì)象模型。為移動(dòng)對(duì)象的最近鄰查詢算法的研究提供了符合實(shí)際的路網(wǎng)環(huán)境。
　　 2．對(duì)基于路網(wǎng)的索引機(jī)制FNR 樹進(jìn)行了改進(jìn)，提出了FNR*樹，為移動(dòng)對(duì)象的最近鄰查詢算法的研究提供了高效的索引支持，降低了檢索移動(dòng)對(duì)象的時(shí)間。
　　 3．提出了基于聚類的移動(dòng)對(duì)象最近鄰查詢算法C_NN。該算法針對(duì)移動(dòng)對(duì)象快速變化的特點(diǎn)，對(duì)查詢點(diǎn)進(jìn)行聚類并計(jì)算出查詢結(jié)果。算法在一定程度上解決了傳統(tǒng)的基于路網(wǎng)