時(shí)空數(shù)據(jù)庫(kù)查詢處理關(guān)鍵技術(shù)研究.pdf

1、移動(dòng)計(jì)算、無(wú)線通信以及定位技術(shù)的快速發(fā)展使得對(duì)各種空間與時(shí)空對(duì)象的存儲(chǔ)和管理成為了現(xiàn)實(shí)需求。大量的應(yīng)用領(lǐng)域(如地理信息系統(tǒng)、智能導(dǎo)航、交通管制、天氣預(yù)報(bào)、軍事、移動(dòng)電子商務(wù)等)均迫切需要有效地查詢這些數(shù)據(jù)對(duì)象。然而，空間與時(shí)空數(shù)據(jù)固有的海量性和復(fù)雜性使得傳統(tǒng)的數(shù)據(jù)庫(kù)查詢處理技術(shù)不能或不能有效地發(fā)揮作用，需要研究新的查詢處理技術(shù)。因此，如何提供各種高效的空間與時(shí)空對(duì)象查詢處理技術(shù)是當(dāng)前時(shí)空數(shù)據(jù)庫(kù)領(lǐng)域的研究熱點(diǎn)之一。 時(shí)空數(shù)據(jù)庫(kù)的查

2、詢效率是衡量時(shí)空數(shù)據(jù)庫(kù)性能的重要指標(biāo)。盡管已有許多的研究學(xué)者致力于這方面的研究，并取得了許多可喜的成果，但距離滿足用戶不斷出現(xiàn)的、復(fù)雜而多樣的查詢要求還有一定的差距，仍有待相關(guān)研究進(jìn)一步的深入。此外，國(guó)內(nèi)開(kāi)展該領(lǐng)域研究的單位還不多，在該領(lǐng)域的研究水平和國(guó)外相比，還存在著一定的差距。因而，適時(shí)開(kāi)展時(shí)空數(shù)據(jù)庫(kù)查詢處理技術(shù)的研究是必需的，有著重要的學(xué)術(shù)價(jià)值和廣闊的應(yīng)用前景。 鑒于此，本文從兩個(gè)方面對(duì)時(shí)空數(shù)據(jù)庫(kù)查詢處理中的關(guān)鍵技術(shù)問(wèn)題進(jìn)

3、行了研究和探索。一是如何有效地處理針對(duì)空間對(duì)象的各類查詢，在這方面，本文主要探討了并行最近鄰查詢、并行Skyline查詢、分支界限Skyline查詢以及相互(即對(duì)稱)最近鄰查詢的處理技術(shù)；二是如何有效地處理針對(duì)歷史移動(dòng)對(duì)象軌跡(即時(shí)空對(duì)象)的各類查詢，在這方面，本文重點(diǎn)討論了κ(≥1)最近鄰(kNN)查詢、歷史連續(xù)kNN(HCkNN)查詢、受限kNN(CkNN)查詢、歷史連續(xù)CkNN(HCCkNN)查詢、相互最近鄰(MNN)查詢以及歷史

4、連續(xù)MNN(HCMNN)查詢的處理技術(shù)。本文的主要貢獻(xiàn)和創(chuàng)新可概括如下： 1)首次提出了多磁盤環(huán)境下基于最佳優(yōu)先的并行κ(≥1)最近鄰查詢算法。這些算法在效率和可擴(kuò)展性方面的性能均大大地優(yōu)于現(xiàn)有的同類算法。 2)首次給出了多磁盤環(huán)境下的并行Skyline查詢處理方法，并用實(shí)驗(yàn)對(duì)其性能進(jìn)行了全面地評(píng)價(jià)和分析。 3)提出了一種存儲(chǔ)最佳的分支界限Skyline查詢算法。該算法既有最佳的I/O代價(jià)(即結(jié)點(diǎn)訪問(wèn)量)和較低的

5、CPu開(kāi)銷，又有最少的內(nèi)存空間耗費(fèi)，并在性能上明顯地好于目前最好的同類算法。 4)探討了歷史移動(dòng)對(duì)象軌跡的kNN查詢和HCkNN查詢的問(wèn)題。遵循最佳優(yōu)先搜索范例，分別提出了關(guān)于靜態(tài)查詢點(diǎn)和移動(dòng)查詢軌跡的kNN查找和H(；kNN查找的處理方法。這些方法在效率和可擴(kuò)展性方面的性能遠(yuǎn)遠(yuǎn)地勝過(guò)已有的同類算法。此外，引入了一個(gè)新穎的距離度量標(biāo)準(zhǔn)，開(kāi)發(fā)了若干個(gè)剪枝啟發(fā)式，設(shè)計(jì)了用于存放HcKNN查詢結(jié)果的κ個(gè)最近列表的更新方法。 5

6、)首次引入并解決了空間對(duì)象的MNN查詢問(wèn)題。形式化定義了這一新穎的MNN查詢類型，并分析其特性；提出了一系列的MNN查詢算法，并通過(guò)實(shí)驗(yàn)評(píng)估其性能。 6)首次引入并討論了歷史移動(dòng)對(duì)象軌跡的CkNN查詢和HCCkNN查詢的問(wèn)題。形式化定義了這些新的查詢類型，分別提出了若干針對(duì)靜態(tài)查詢點(diǎn)和移動(dòng)查詢軌跡的CkNN查找和HCCkNN查找的處理方法，并對(duì)這些方法進(jìn)行了全面的性能評(píng)價(jià)和分析比較。 7)首次引入并研究了歷史移動(dòng)對(duì)象軌跡