路網(wǎng)中考慮運動狀態(tài)的連續(xù)K近鄰查詢算法研究.pdf

1、在數(shù)據(jù)庫研究領(lǐng)域中,連續(xù)K近鄰查詢處理技術(shù)是受很多學(xué)者關(guān)注的一個問題,它在實際生活中有很多應(yīng)用,比如交通調(diào)度控制、數(shù)字戰(zhàn)場、個人位置服務(wù)等系統(tǒng)都要對移動用戶的相關(guān)位置或軌跡信息進行管理,然而在這些應(yīng)用中管理連續(xù) K近鄰查詢服務(wù)的空間數(shù)據(jù)和空間對象的訪問等都被限制在空間網(wǎng)絡(luò)中,比如在路網(wǎng)中。而一些存在的查詢處理方法對于動態(tài)查詢處理問題是無法解決和直接使用的,需要研究適合動態(tài)環(huán)境下的連續(xù)K近鄰查詢處理技術(shù)。因此,路網(wǎng)中移動對象連續(xù)K近鄰查詢

2、處理也是實際應(yīng)用的迫切要求,研究如何提供各種高效的路網(wǎng)移動對象查詢處理技術(shù)是具有一定的研究價值和實際應(yīng)用價值。
　　在現(xiàn)有的移動對象數(shù)據(jù)庫索引和查詢處理技術(shù)等方面的最新成果基礎(chǔ)上,從移動對象運動軌跡和模式分析入手,對空間索引技術(shù)、動態(tài)環(huán)境下不確定性對象處理技術(shù)以及K近鄰查詢處理方法進行了深入研究,針對在連續(xù)K近鄰查詢處理技術(shù)中存在的問題,提出解決方案,進一步提出了路網(wǎng)中移動對象的連續(xù) K近鄰查詢處理技術(shù)和不確定性對象的索引方法,以

3、解決實際位置服務(wù)查詢應(yīng)用系統(tǒng)中的關(guān)鍵技術(shù)問題。具體的工作和創(chuàng)新點包括如下:
　　由于數(shù)據(jù)對象在路網(wǎng)中頻繁而任意移動,對象位置的頻繁更新使得準確和有效地處理連續(xù) K近鄰查詢是很復(fù)雜的。為了解決這個問題,本文根據(jù)移動對象和查詢點之間的相對移動狀態(tài),提出了一個移動狀態(tài)(Moving State of Object,MSO)模型,表示出移動對象與查詢點的移動狀態(tài)。在這個模型的幫助下,提出了一個新的候選對象處理(Object Candida

4、te Processing,OCP)算法,用剪枝階段和精煉階段可以極大減少重復(fù)查詢代價,并通過模擬實驗進行了證明。
　　在一些應(yīng)用中(比如:當(dāng)我在行走時找到接下來5分鐘內(nèi)離我最近的出租車),它是不需要獲得準確的結(jié)果集。對于這些應(yīng)用,介紹了一個新穎的技術(shù),基于移動狀態(tài)的近鄰連續(xù) K近鄰查詢處理( Moving state based Approximate CKNN,MACKNN),首次描述了一個不定對象的移動狀態(tài)(MSUO)模型,

5、通過移動對象和查詢點的速度區(qū)間提出一個移動度方法來決定對象與查詢點之間的移動狀態(tài)。在MSUO模型的幫助下,提出的MACKNN技術(shù)由兩個階段組成,它們是剪枝和精煉階段,剪枝階段用來通過計算在給定時間區(qū)間內(nèi)移動對象與查詢點 q之間的距離去剪掉不合格的對象。精煉階段是設(shè)計來確定時間子區(qū)間,在這個子區(qū)間內(nèi)查詢結(jié)果是一定的。實驗結(jié)果顯示就運行時間和準確度而言,我們的方法更優(yōu)于CKNN和IMA算法,并保持一定的準確程度。
　　為了處理實際應(yīng)用

6、中不定速度的移動對象查詢處理,研究了在所給時間區(qū)間內(nèi)路網(wǎng)中不定速度的移動對象上處理CKNN查詢的問題,提出了一個距離區(qū)間模型(DIM)來計算在一個時間點上以不定速度和方向運動的一個移動對象的距離區(qū)間,它主要包括一個移動對象與查詢點之間的最小和最大距離。同時為了有效處理移動對象信息更新,提出了一種有效的移動對象索引方法,稱為TPRuv-樹,在DIM計算方法和TPRuv-樹的幫助下,提出了一個PVKNN算法有效地處理CKNN查詢。PVKNN