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

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

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

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

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

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

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

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