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

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

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

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

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

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

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