[發明專利]一種基于云計算環境的分布并行Skyline查詢方法

有效

• 申請號: 201110327433.4
• 申請日: 2011-10-25
• 公開（公告）號: CN102314521A
• 公開（公告）日: 2012-01-11
• 發明（設計）人: 王意潔;王媛;鄧瑞鵬;裴曉強;李小勇;孫偉東;馬行空
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;H04L29/08
• 代理公司: 國防科技大學專利服務中心 43202
• 代理人: 郭敏

技術領域

本發明涉及Skyline查詢的分布并行處理方法，尤其是基于云計算環境的高效可靠的分布并行Skyline查詢方法。

背景技術

Skyline查詢是海量數據管理領域亟待解決的核心問題之一。Skyline查詢是指從給定的一個D維的數據對象集合S中選擇一個子集，該子集中的任意一個數據對象都不能被S中的任意一個其他數據對象所控制。所謂控制關系是指在D維的數據對象集合S中，如果數據對象p至少在某一維度上優于另一個數據對象q，而且數據對象p在其他維度上都不比數據對象q差(p優于或等于q)，那么數據對象p能夠控制數據對象q。Skyline查詢是目前解決多目標優化問題的典型方法之一，Skyline查詢已經成為數據分析和信息提取的重要技術手段，在城市導航、市場分析、環境監控等諸多領域都有著重要應用。

近年來，隨著計算機技術、網絡技術和通信技術的快速發展，人們獲取、存儲和傳遞數據的能力日益增強，數據的規模急劇膨脹，“大數據”作為信息爆炸的產物應運而生。隨著數據集規模的不斷增大，Skyline查詢的數據處理變得更加復雜，對存儲資源和計算資源的需求也急劇增長，Skyline查詢的處理效率逐漸成為影響數據分析和信息提取效果的關鍵因素。

隨著集群計算、網格計算、P2P計算等網絡計算模式的不斷發展，分布式并行計算技術已經日趨成熟，并逐漸成為提高海量數據處理效率的有效技術途徑之一。云計算是分布計算、并行計算和網格計算的發展，是一種新的分布式并行計算模式。它將計算任務分布在大量計算機構成的資源池上，使各種應用系統能夠根據需要獲取計算力、存儲空間和各種軟件服務。將云計算技術與海量數據的Skyline查詢相結合，可以通過開發查詢計算的并行性來提高查詢處理效率。

盡管隨著技術的進步，各種軟硬件資源的可靠性得到了顯著提高，但是，隨著云計算的資源規模的不斷擴大，資源的失效概率明顯上升。此外，為了有效降低維護成本，失效資源不是及時更新，而是成批維護的。在云計算環境下，資源失效是一種常態行為。

現有的Skyline查詢方法主要關注查詢處理過程及其查詢結果的正確性，無法及時處理節點失效情況，無法有效兼顧Skyline查詢處理的高效性和可靠性。因此，如何針對海量數據及其Skyline查詢的本質特點，結合云計算環境的資源特點，設計高效可靠的分布并行Skyline查詢方法，保證Skyline查詢處理的效率和查詢結果的正確性，已經成為并行與分布處理領域的熱點研究問題。

發明內容

本發明要解決的技術問題是：針對現有的Skyline查詢方法無法有效處理查詢處理過程中的節點失效的問題，提出一種基于云計算環境的分布并行Skyline查詢方法，有效控制節點失效對分布并行Skyline查詢處理過程的影響，保證Skyline查詢處理的高效性和可靠性、以及查詢結果的正確性。

本發明技術方案包括以下步驟：

第一步，構建一個云計算環境，它由多個節點構成，每個節點都是一臺可獨立運行的計算機，各節點通過網絡設備互連。

云計算環境中的節點分為兩類：門戶節點和計算節點。云計算環境包括一個門戶節點，負責與用戶交互，接收用戶提交的查詢請求并轉發給計算節點，接收計算節點的查詢處理結果并返回給用戶。云計算環境包括N個計算節點(N為正整數)，它們負責存儲原始數據集并執行查詢處理任務，并向門戶節點返回查詢處理結果。為了提高可靠性，同時降低系統成本，采用互為備份方式對計算節點進行容錯處理，以避免計算節點失效對Skyline查詢處理的影響?；閭浞莘绞绞侵该總€計算節點是其他所有計算節點的備份節點，其他所有計算節點上的原始數據集的副本都存儲在該計算節點上；每個計算節點有N-1個備份節點，計算節點上的原始數據集的副本存儲在其N-1個備份節點上。門戶節點和計算節點上均安裝有操作系統、TCP/IP協議軟件，配置了網絡環境。

門戶節點上安裝有任務管理程序和結果回收程序。任務管理程序接收用戶提交的Skyline查詢請求，向各計算節點轉發Skyline查詢請求。結果回收程序負責接收計算節點的查詢處理結果并返回給用戶。計算節點上安裝有查詢處理程序和故障處理程序。查詢處理程序負責接收來自門戶節點的Skyline查詢請求，并對計算節點上存儲的原始數據集進行Skyline查詢處理。故障處理程序負責定期對鄰居節點進行故障檢測，并進行故障修復。設計算節點的編號為i(i＝1，2，…，N)，當1≤i≤N-1時，計算節點i的鄰居節點為計算節點i+1；當i＝N時，計算節點i的鄰居節點為計算節點1。