復(fù)雜空間環(huán)境下的新型空間查詢處理技術(shù)研究.pdf

1、隨著空間定位和移動(dòng)通信等技術(shù)的發(fā)展，以及人們對(duì)空間信息日益強(qiáng)烈的需求，空間數(shù)據(jù)管理技術(shù)在近些年來(lái)獲得了極大的關(guān)注。查詢處理技術(shù)是空間數(shù)據(jù)管理領(lǐng)域最常見的和最重要的應(yīng)用。例如，司機(jī)會(huì)查找離自己最近的餐館信息，以及自己油箱內(nèi)的油能夠到達(dá)的加油站等。目前，已有一些研究對(duì)多種空間查詢提出解決方案，包括高效的索引技術(shù)以及高效的查詢策略等，這些解決方案都限定在比較單一的空間環(huán)境中。然而，真實(shí)世界中空間環(huán)境復(fù)雜多樣，例如，空間中存在障礙物，地面上存在

2、路徑限制對(duì)象的運(yùn)動(dòng)等。已有的技術(shù)往往沒(méi)有充分考慮復(fù)雜空間環(huán)境的特點(diǎn)，無(wú)法準(zhǔn)確、高效地在這樣復(fù)雜的空間中處理空間查詢。因此，亟需針對(duì)不同的空間環(huán)境定義一些新的空間模型，并且設(shè)計(jì)新的距離度量機(jī)制，進(jìn)而對(duì)空間查詢有針對(duì)性地設(shè)計(jì)新型查詢技術(shù)。
　　本文對(duì)已有空間環(huán)境和已有的查詢處理技術(shù)進(jìn)行了分析和綜述。在此基礎(chǔ)上，本文深入研究了幾種復(fù)雜空間環(huán)境，并且基于這些空間環(huán)境針對(duì)幾種查詢?cè)O(shè)計(jì)了新型的高效查詢策略。本文的貢獻(xiàn)主要包括以下幾個(gè)方面:

3、r>　　針對(duì)半限制空間內(nèi)移動(dòng)對(duì)象邏輯軌跡近鄰對(duì)查詢，本文提出了高效的解決技術(shù)。半限制空間是從室內(nèi)等有限制空間環(huán)境中抽象出來(lái)的一種新的空間環(huán)境，該環(huán)境將空間劃分為多個(gè)離散的區(qū)域，無(wú)需考慮對(duì)象在同一區(qū)域內(nèi)的距離，不同區(qū)域之間通過(guò)物理路徑連接。半限制空間內(nèi)的軌跡是一條位置標(biāo)號(hào)的序列，每個(gè)點(diǎn)代表一個(gè)邏輯區(qū)域。不同邏輯區(qū)域之間的距離預(yù)先由系統(tǒng)給定，反映兩區(qū)域之間的實(shí)際連通距離。本文針對(duì)半限制空間內(nèi)邏輯軌跡近鄰對(duì)查詢展開深入研究。為了提高基本方法的

4、解決效率，本文提出基于軌跡共現(xiàn)度的過(guò)濾策略和基于長(zhǎng)度偏移比的過(guò)濾策略，避免了對(duì)兩兩軌跡對(duì)的比較，從而提高了查詢效率。
　　針對(duì)路網(wǎng)空間內(nèi)無(wú)線廣播模式中的k近鄰，反最近鄰和范圍查詢，本文提出了基于高效索引技術(shù)的查詢處理方法。無(wú)線廣播模式中，服務(wù)器不停地向外廣播數(shù)據(jù)，客戶端根據(jù)需要接收數(shù)據(jù)，客戶端無(wú)法向上傳遞數(shù)據(jù)。在無(wú)線廣播模式中執(zhí)行空間查詢想要達(dá)到的效果是從發(fā)起查詢時(shí)刻到得到結(jié)果時(shí)刻的處理延遲較小，以及客戶端接收數(shù)據(jù)的活躍時(shí)間較少。

5、本文的處理機(jī)制將路網(wǎng)空間劃分為多個(gè)小的區(qū)域，然后對(duì)每個(gè)區(qū)域預(yù)計(jì)算該區(qū)域到空間中每個(gè)區(qū)域距離的上下限，在此基礎(chǔ)上對(duì)這些區(qū)域建立索引。由于該索引中包含一些預(yù)計(jì)算的信息，因此通過(guò)接收索引，用戶可以迅速判定自己所需要的數(shù)據(jù)塊。并且，通過(guò)合理地組織索引，能夠使得需要接收的數(shù)據(jù)包數(shù)量盡可能地少，從而達(dá)到活躍時(shí)間和處理延遲的平衡。在此索引基礎(chǔ)上，針對(duì)路網(wǎng)上的k近鄰查詢，反最近鄰查詢和范圍查詢，分別設(shè)計(jì)了高效的查詢處理方法。
　　針對(duì)障礙空間內(nèi)概

6、率可見k近鄰查詢，本文提出了高效的剪枝和驗(yàn)證方法。在障礙空間內(nèi)，對(duì)象之間的距離以可見距離衡量。由于測(cè)量設(shè)備誤差、網(wǎng)絡(luò)傳輸延遲等因素，對(duì)象的位置往往是不確定的，對(duì)這類位置不確定對(duì)象以概率限定矩形和概率密度函數(shù)建模。針對(duì)這種不確定對(duì)象的可見k近鄰查詢，提出了一種剪枝-求精的處理框架。根據(jù)空間對(duì)象屬性，設(shè)計(jì)了k-界限剪枝，可見質(zhì)心剪枝以及不可見對(duì)象剪枝方法，將不可能成為結(jié)果的對(duì)象剪掉，獲取一個(gè)較小的候選集。然后，對(duì)候選集合進(jìn)行求精，通過(guò)采樣方

7、法以及高效的基于上下限的增量求精方法，得到最終結(jié)果集。
　　針對(duì)障礙空間內(nèi)移動(dòng)可見k近鄰查詢，本文提出了剪枝-求精的高效處理機(jī)制。其中，查詢點(diǎn)和查詢對(duì)象都在不規(guī)律運(yùn)動(dòng)。本文提出一個(gè)新穎的處理機(jī)制，對(duì)每個(gè)對(duì)象（包括查詢對(duì)象）都賦予一個(gè)安全區(qū)域，在T時(shí)間內(nèi)保證所有對(duì)象都在其安全區(qū)域內(nèi)，每隔T時(shí)間需要更新全部對(duì)象的位置。在此基礎(chǔ)上采用剪枝-求精的查詢框架。首先利用安全區(qū)域的空間特性，提出了基于安全區(qū)域的空間距離的剪枝方法。然后，通過(guò)對(duì)不