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

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

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

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

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

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

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