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

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

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

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

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

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

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

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