面向不確定對象的新型空間查詢處理技術(shù)研究.pdf

1、空間數(shù)據(jù)庫的研究始于20世紀(jì)70年代的地圖制圖與遙感圖像處理領(lǐng)域，其目的是為了有效地利用衛(wèi)星遙感資源迅速繪制出各種專題地圖。隨著地理信息系統(tǒng)、計算機(jī)輔助設(shè)計與制造、機(jī)器人、多媒體系統(tǒng)、數(shù)字地球、移動通信及定位服務(wù)等領(lǐng)域的發(fā)展，對空間數(shù)據(jù)庫的研究越來越受到人們的重視。特別是基于位置的服務(wù)，為空間數(shù)據(jù)庫上的數(shù)據(jù)處理帶來了巨大的挑戰(zhàn)。如何對位置服務(wù)中的對象進(jìn)行高效查詢處理，是決定空間數(shù)據(jù)庫應(yīng)用前景的關(guān)鍵問題之一，得到了學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注

2、。目前，已有一些針對位置服務(wù)應(yīng)用的空間查詢處理技術(shù)的相關(guān)研究。由于測量手段的不準(zhǔn)確性以及數(shù)據(jù)本身的性質(zhì)導(dǎo)致某些空間應(yīng)用中的查詢對象具有不確定性，如何針對一些新型查詢類型中具有不確定性的目標(biāo)對象進(jìn)行建模以及查詢處理，是目前空間數(shù)據(jù)庫領(lǐng)域中亟待解決的熱點問題。
　　本文對空間數(shù)據(jù)管理中的不確定性現(xiàn)象和問題進(jìn)行了歸納和總結(jié)，并對空間數(shù)據(jù)庫中不確定性數(shù)據(jù)管理的研究現(xiàn)狀進(jìn)行了分析和綜述。我們將空間對象的不確定性在宏觀上分為位置不確定性和存在

3、不確定性，針對這些不確定性，在索引建立，最近對查詢及組近鄰查詢等方面提出了新的模型和解決方法，建立了一套有特色的處理框架。這些技術(shù)可以有效的提高空間數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)管理能力和處理效率，從而支持復(fù)雜環(huán)境下的新型空間查詢應(yīng)用。
　　具體的，本文對多種不同類型的空間查詢處理技術(shù)進(jìn)行了深入研究。這些查詢包括最近對查詢、范圍最近對查詢、組最近鄰查詢及組最近組查詢等，涵蓋了空間數(shù)據(jù)庫中面向不確定對象的數(shù)據(jù)建模、索引構(gòu)建和查詢優(yōu)化的關(guān)鍵問題，主

4、要工作包括以下幾個方面:
　　(1)研究了空間數(shù)據(jù)庫中面向位置不確定對象的最近對查詢問題，提出了Top-K概率最近鄰查詢處理算法以及概率閾值最近鄰查詢處理算法。對空間數(shù)據(jù)庫中的位置不確定對象的特點進(jìn)行了分析，建立了相應(yīng)的數(shù)據(jù)模型，并提出了一種有效的聚簇索引結(jié)構(gòu)?；谒饕Y(jié)構(gòu)以及最近對查詢特點，提出并證明了最近對查詢過程中可采用的優(yōu)化策略，并將這些優(yōu)化策略有效地應(yīng)用到具體的查詢處理算法中，提高了概率最近對查詢處理效率。
　　(

5、2)研究了面向位置不確定對象的范圍最近對查詢問題，提出了帶有兩種范圍約束的概率最近對查詢處理算法。對空間數(shù)據(jù)庫中面向位置不確定對象的范圍最近對查詢處理方法進(jìn)行了研究。建立了基于U樹結(jié)構(gòu)的聚簇U樹索引，提出了面向位置不確定對象范圍最近對查詢定義。在運(yùn)用空間剪枝技術(shù)和概率剪枝技術(shù)來提高性能的基礎(chǔ)上，設(shè)計了高效查詢處理算法對帶有強(qiáng)范圍約束和弱范圍約束的范圍最近對查詢進(jìn)行高效處理，在保證查詢的準(zhǔn)確性的同時減少了磁盤訪問。
　　(3)研究了

6、空間數(shù)據(jù)庫中面向存在不確定對象的組最近鄰查詢問題，提出了概率組最近鄰查詢處理算法。提出了基于存在不確定性的數(shù)據(jù)模型，并在此模型的基礎(chǔ)上，設(shè)計了一種擴(kuò)展式R樹索引，用以大量減少概率組最近鄰查詢處理的時間。此外，根據(jù)存在不確定對象的特點，設(shè)計了兩種基于排他概率的查詢處理方法，即基于剪枝集和基于候選集的查詢處理算法，從而使其即滿足查詢準(zhǔn)確性要求又提高了查詢處理效率。
　　(4)研究了約束組最近組查詢問題，并分別給出了面向確定對象的基本約

7、束組最近組查詢算法和面向存在不確定對象的概率約束組最近組查詢算法。根據(jù)某些特殊應(yīng)用的需求，在組最近組查詢的基礎(chǔ)上給出了約束組最近組的查詢語義。研究了一種基于約束聚簇的約束組最近組查詢方法，并通過高效剪枝技術(shù)提高了查詢效率。在面向確定對象的約束組最近組查詢基礎(chǔ)上，提出兩種面向存在不確定對象的概率約束組最近組查詢語義，并給出了相應(yīng)查詢處理方法以減少約束組最近組查詢的搜索代價。
　　總之，本文從空間查詢中涉及到的不確定對象的典型特征和挑