移動(dòng)對象軌跡的最近鄰居查詢研究.pdf

1、隨著無線通訊和位置定位系統(tǒng)的發(fā)展，移動(dòng)對象數(shù)據(jù)庫(MOD)變得越來越重要，也對數(shù)據(jù)庫研究提出了極大的挑戰(zhàn)?；跁r(shí)間和空間的查詢算法成為一些基于位置的服務(wù)急需解決的問題。比如：交通控制，近鄰信息訪問和對野生動(dòng)物遷徙特性的分析等。而其中一個(gè)重要的查詢類型就是七最近鄰居(kNN)查詢。它主要用來查詢離某一移動(dòng)對象最近的七個(gè)軌跡。據(jù)我們所知，在已有的研究文獻(xiàn)中，研究學(xué)者們主要處理的是對于一系列連續(xù)移動(dòng)點(diǎn)的將來或者當(dāng)前位置的查詢，這些查詢或者基于

2、靜態(tài)的查詢點(diǎn)或者基于連續(xù)移動(dòng)的查詢點(diǎn)。但是對于歷史移動(dòng)對象軌跡的最近鄰居查詢卻很少。 基于此，在本文中，首先，我們提出了兩種基于最佳優(yōu)先(Best-First)策略的算法：BFPkNN和BFTkNN。分別用來處理靜態(tài)查詢點(diǎn)以及移動(dòng)軌跡的七最近鄰居(kNN)。并且為了減少內(nèi)存消耗和CPU時(shí)間，本文給出了一些有效的剪枝策略。這些剪枝策略能夠有效的避免訪問那些不可能包含最終結(jié)果的節(jié)點(diǎn)，也能剔除掉那些不會(huì)成為最終結(jié)果的跡線段。其次，我們

3、還提出了在歷史移動(dòng)對象軌跡上處理連續(xù)七最近鄰居查詢的兩個(gè)算法：HC<,P>-kNN和HCT<,T>-kNN。同時(shí)我們分析并給出了在連續(xù)kNN查詢中常用的維護(hù)和更新k個(gè)最近鄰居列表(kNearestLists)算法。再次，本文提出了在存儲(chǔ)有歷史移動(dòng)對象軌跡的基于R樹的索引結(jié)構(gòu)上進(jìn)行受限k最近鄰居(CkNN)查詢的概念，以及有效的處理方法。具體來說，為了有效處理CkNN我們提出了區(qū)域查詢和kNN查詢的依次查詢方法以及在kNN查詢中整合區(qū)域查