[發(fā)明專利]基于垂直劃分模式的分布并行Skyline查詢方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201110327359.6
• 申請(qǐng)日: 2011-10-26
• 公開（公告）號(hào): CN102323957A
• 公開（公告）日: 2012-01-18
• 發(fā)明（設(shè)計(jì)）人: 王意潔;王媛;鄧瑞鵬;裴曉強(qiáng);李小勇;孫偉東;馬行空
• 申請(qǐng)（專利權(quán)）人: 中國人民解放軍國防科學(xué)技術(shù)大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 國防科技大學(xué)專利服務(wù)中心 43202
• 代理人: 郭敏

技術(shù)領(lǐng)域

本發(fā)明涉及Skyline查詢的分布并行處理方法，尤其是基于數(shù)據(jù)垂直劃分模式的高效分布并行Skyline查詢方法。

背景技術(shù)

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

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

隨著集群計(jì)算、網(wǎng)格計(jì)算、對(duì)等計(jì)算、云計(jì)算等網(wǎng)絡(luò)計(jì)算模式的不斷發(fā)展，分布并行計(jì)算技術(shù)已經(jīng)日趨成熟，并逐漸成為提高海量數(shù)據(jù)處理效率的有效技術(shù)途徑之一。分布并行計(jì)算將計(jì)算任務(wù)分布在大量計(jì)算機(jī)構(gòu)成的資源池上，使各種應(yīng)用系統(tǒng)能夠根據(jù)需要獲取計(jì)算能力、存儲(chǔ)空間和各種軟件服務(wù)。將分布并行計(jì)算技術(shù)與海量數(shù)據(jù)的Skyline查詢相結(jié)合，可以通過開發(fā)查詢計(jì)算的并行性來提高查詢處理效率。

目前，數(shù)據(jù)分布的模式主要包括水平劃分模式和垂直劃分模式。水平劃分模式是指數(shù)據(jù)分布在多個(gè)節(jié)點(diǎn)上，每個(gè)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)是整個(gè)數(shù)據(jù)集的一部分，且各節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)是覆蓋全部維度的完整的數(shù)據(jù)對(duì)象。垂直劃分模式是指數(shù)據(jù)分布在多個(gè)節(jié)點(diǎn)上，每個(gè)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)是整個(gè)數(shù)據(jù)集的一部分，且各節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)是所有數(shù)據(jù)對(duì)象在一個(gè)或者多個(gè)維度上的所有數(shù)據(jù)，而不是完整的數(shù)據(jù)對(duì)象。現(xiàn)有的基于垂直劃分模式的分布并行Skyline查詢方法(W.-T.Balke，U.Güntzer，J.Zheng.Efficient?Distributed?Skylining?for?Web?Information?Systems.In?Proc?of?the?Int.Conf.on?Extending?Database?Technology(EDBT’04)，Heraklion，Crete，Greece，2004，256-273.)將不同維度的數(shù)據(jù)分布存儲(chǔ)在各計(jì)算節(jié)點(diǎn)上，各計(jì)算節(jié)點(diǎn)負(fù)責(zé)對(duì)各自存儲(chǔ)的維度數(shù)據(jù)進(jìn)行排序，然后統(tǒng)一發(fā)送給協(xié)調(diào)節(jié)點(diǎn)，協(xié)調(diào)節(jié)點(diǎn)負(fù)責(zé)基于各計(jì)算節(jié)點(diǎn)的排序結(jié)果進(jìn)行Skyline查詢處理。由此可見，大量的查詢處理任務(wù)主要集中在協(xié)調(diào)節(jié)點(diǎn)，Skyline查詢處理的并行性沒有得到充分開發(fā)，計(jì)算節(jié)點(diǎn)的數(shù)據(jù)處理能力沒有得到充分利用，從而導(dǎo)致分布并行Skyline查詢方法的處理效率十分有限，難以充分滿足海量數(shù)據(jù)分析和信息提取的實(shí)際需求。

因此，如何針對(duì)海量數(shù)據(jù)及其Skyline查詢的本質(zhì)特點(diǎn)，結(jié)合分布并行計(jì)算環(huán)境的資源特點(diǎn)，設(shè)計(jì)基于垂直劃分模式的高效分布并行Skyline查詢方法，保證Skyline查詢處理的效率和查詢結(jié)果的正確性，已經(jīng)成為并行與分布處理領(lǐng)域的熱點(diǎn)研究問題。

發(fā)明內(nèi)容

本發(fā)明要解決的技術(shù)問題是：針對(duì)現(xiàn)有的基于垂直劃分模式的分布并行Skyline查詢方法處理效率不高的問題，提出一種基于垂直劃分模式的分布并行Skyline查詢方法，充分開發(fā)Skyline查詢處理的并行性，在保證查詢結(jié)果的正確性的前提下，顯著提高Skyline查詢處理的效率。

本發(fā)明技術(shù)方案包括以下步驟：

第一步，構(gòu)建一個(gè)分布并行計(jì)算環(huán)境，它由多個(gè)節(jié)點(diǎn)構(gòu)成，每個(gè)節(jié)點(diǎn)都是一臺(tái)可獨(dú)立運(yùn)行的計(jì)算機(jī)，各節(jié)點(diǎn)通過網(wǎng)絡(luò)設(shè)備互連。

分布并行計(jì)算環(huán)境中的節(jié)點(diǎn)分為兩類：協(xié)調(diào)節(jié)點(diǎn)和計(jì)算節(jié)點(diǎn)。分布并行計(jì)算環(huán)境包括一個(gè)協(xié)調(diào)節(jié)點(diǎn)，協(xié)調(diào)節(jié)點(diǎn)負(fù)責(zé)存儲(chǔ)原始數(shù)據(jù)集中的所有數(shù)據(jù)對(duì)象的編號(hào)，負(fù)責(zé)與用戶交互，接收用戶提交的查詢請(qǐng)求，向各計(jì)算節(jié)點(diǎn)分發(fā)查詢處理任務(wù)和收集查詢處理結(jié)果，并向用戶返回查詢結(jié)果。分布并行計(jì)算環(huán)境包括N個(gè)計(jì)算節(jié)點(diǎn)(N是原始數(shù)據(jù)集中數(shù)據(jù)對(duì)象的維度數(shù)目，N為正整數(shù))，每個(gè)計(jì)算節(jié)點(diǎn)負(fù)責(zé)存儲(chǔ)原始數(shù)據(jù)集的一個(gè)維度上的所有數(shù)據(jù)，計(jì)算節(jié)點(diǎn)執(zhí)行查詢處理任務(wù)，并向協(xié)調(diào)節(jié)點(diǎn)返回查詢處理結(jié)果。協(xié)調(diào)節(jié)點(diǎn)和計(jì)算節(jié)點(diǎn)上均安裝有操作系統(tǒng)、TCP/IP協(xié)議軟件，配置了網(wǎng)絡(luò)環(huán)境。