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

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

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

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

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

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

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

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