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

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

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

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

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

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

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