一種分布式環(huán)境中的二分式多層網(wǎng)格skyline算法

丁日強(qiáng)

渤海大學(xué) 信息科學(xué)與技術(shù)學(xué)院，遼寧 錦州 121000

一種分布式環(huán)境中的二分式多層網(wǎng)格skyline算法

丁日強(qiáng)

渤海大學(xué) 信息科學(xué)與技術(shù)學(xué)院，遼寧 錦州 121000

1 引言

近年來，由于skyline在多維數(shù)據(jù)集中的諸多應(yīng)用，人們對(duì)skyline查詢處理的興趣已經(jīng)越來越大。給定一個(gè)數(shù)據(jù)集P包含對(duì)象P={P1，P2，…，Pn}，skyline查詢處理可以返回所有Pi值，其中對(duì)象Pi不受另一個(gè)對(duì)象Pj控制（所謂控制關(guān)系是指：如果對(duì)象p至少在某一維上優(yōu)于另一對(duì)象q，而在其他維上都不比對(duì)象q差，則說p能夠控制q）。之前的研究主要側(cè)重于如何獲得高效的集中式skyline查詢算法，像文獻(xiàn)[1-4]所提到的算法均是這樣的。然而，在實(shí)際中，大量的獨(dú)立數(shù)據(jù)往往是存儲(chǔ)在不同的分布式服務(wù)器上的。圖1顯示了在分布式環(huán)境下的skyline查詢：skyline查詢是由用戶通過查詢服務(wù)器（Query Server，QS）發(fā)起的，skyline查詢的分析結(jié)果是通過收集所有連接服務(wù)器的數(shù)據(jù)得到的。比如現(xiàn)在要買一輛車，就是一種類似于分布式環(huán)境下的skyline查詢，需要根據(jù)各輛車的價(jià)格，質(zhì)量，安全性等多個(gè)標(biāo)準(zhǔn)，從各個(gè)不同的售車網(wǎng)站獲得各種信息，最終買到滿意的車輛。這種多重標(biāo)準(zhǔn)信息的綜合捕捉就需要利用一種分布式體系結(jié)構(gòu)來解決，從而避免產(chǎn)生太大的數(shù)據(jù)訪問。

圖1 分布式環(huán)境下的skyline查詢示意圖

處理分布式skyline查詢最簡(jiǎn)單的辦法就是發(fā)送查詢要求給所有連接的本地服務(wù)器，然后各個(gè)本地服務(wù)器自行處理查詢要求，并將處理結(jié)果反饋給查詢服務(wù)器（QS），查詢服務(wù)器（QS）綜合收到的查詢結(jié)果得出一個(gè)最終的全局skyline查詢結(jié)果。這種方法需要傳輸和處理大量不必要的重疊數(shù)據(jù)，這些數(shù)據(jù)是本地skyline查詢要利用的數(shù)據(jù)，而不是全局skyline查詢要利用的數(shù)據(jù)。Joao B等人在文獻(xiàn)[5]中提出了一種基于網(wǎng)格的分布式skyline查詢處理策略（AGiDS），使用基于網(wǎng)格的數(shù)據(jù)結(jié)構(gòu)，獲得每個(gè)服務(wù)器中的數(shù)據(jù)。該方法的思想是發(fā)送包含本地skyline數(shù)據(jù)的信息元組給查詢服務(wù)器（QS），而不是發(fā)送本地skyline數(shù)據(jù)給查詢服務(wù)器（QS），在查詢服務(wù)器（QS）中被控制的局部信息元組首先被淘汰，然后只有未受控制的信息元組中的局部skyline查詢數(shù)據(jù)傳送到查詢服務(wù)器（QS）中。但是，如果發(fā)送到查詢服務(wù)器（QS）的本地服務(wù)器信息元組有重疊，很多不必要的數(shù)據(jù)就需要被處理。

在本文中，提出了一種在分布式環(huán)境中的二分式多層網(wǎng)格skyline查詢算法（DMLG）。該方法假定每個(gè)服務(wù)器共享一個(gè)共同的網(wǎng)格結(jié)構(gòu)，查詢服務(wù)器（QS）首先收集包含本地skyline數(shù)據(jù)的信息元組，如果有的信息元組是重疊的，采用的方法是建立一個(gè)基于重疊信息元組的多層網(wǎng)格，利用這種多層網(wǎng)格機(jī)制，很多不必要的本地?cái)?shù)據(jù)在轉(zhuǎn)移到查詢服務(wù)器進(jìn)行處理之前就會(huì)被過濾掉，所以會(huì)大大提高查詢的效率。

2 相關(guān)工作

對(duì)于skyline查詢計(jì)算，一般分為集中式skyline查詢計(jì)算和分布式skyline查詢計(jì)算。集中式skyline查詢計(jì)算提出較早，也已經(jīng)有了較深入的研究，已經(jīng)有了許多有效的skyline查詢計(jì)算的算法，例如塊嵌套環(huán)算法（BNL）、排序過濾算法（SFS）、最近鄰算法（NN）等等。文獻(xiàn)[1]中提出了塊嵌套環(huán)算法（BNL），BNL算法在內(nèi)存中用一個(gè)窗口保存那些暫時(shí)不被任何其他點(diǎn)所控制的點(diǎn)，BNL會(huì)把窗口組織為一個(gè)自組織列表，這種方法是對(duì)數(shù)據(jù)庫中所有點(diǎn)兩兩比較的一種最簡(jiǎn)單的優(yōu)化方法；文獻(xiàn)[1]中同時(shí)提出了分治法（D&C），D&C的思想是每次將數(shù)據(jù)集沿某一維分成D1和D2兩個(gè)部分，分別計(jì)算D1與D2上的skyline查詢結(jié)果，采取的方法是在D1和D2上分別遞歸調(diào)用D&C算法，直到每一個(gè)子部分都劃分到足夠小，小到能快速計(jì)算出skyline查詢結(jié)果為止，再將D1和D2上的skyline結(jié)果歸并在一起，除去不符合條件的點(diǎn)，最終得到整個(gè)數(shù)據(jù)集的skyline查詢結(jié)果。文獻(xiàn)[2]中提出了排序過濾算法（SFS），其思想是將全部數(shù)據(jù)點(diǎn)按單調(diào)函數(shù)排序，任何一個(gè)排在前面的點(diǎn)都不會(huì)被排在后面的點(diǎn)所控制。經(jīng)過排序之后再使用 BNL算法；文獻(xiàn)[3]中提出了最近鄰算法（NN），NN算法是第一個(gè)用戶友好的 skyline查詢算法，其基本思想是利用搜索到的最近鄰居來遞歸地劃分?jǐn)?shù)據(jù)空間，同時(shí)需要對(duì)全部待測(cè)數(shù)據(jù)集建立一個(gè)R-tree索引，NN算法能夠順序返回用戶規(guī)定的skyline點(diǎn)，具有較好的用戶友好性。文獻(xiàn)[4]中提出了另一種集中式skyline查詢算法：分枝界限算法（BBS），BBS算法與NN算法相似之處是該算法也是基于最近鄰搜索的，而且同樣采用了R樹對(duì)數(shù)據(jù)進(jìn)行索引，而且可以通過改變最小距離公式很好地適應(yīng)用戶的不同需求。因此，從性能的各個(gè)方面來講，BBS被認(rèn)為是當(dāng)前最優(yōu)的集中式skyline查詢計(jì)算算法。

然而，實(shí)際中的數(shù)據(jù)量很大，數(shù)據(jù)源很多且在距離上一般會(huì)相距較遠(yuǎn)，這時(shí)把所有數(shù)據(jù)放在一個(gè)單獨(dú)的服務(wù)器上存儲(chǔ)和處理就不是一個(gè)理想的方法了。文獻(xiàn)[6]提出了解決在多個(gè)分布式來源下的skyline查詢算法，算法的基本關(guān)系是垂直分區(qū)的，即每個(gè)服務(wù)器只保留關(guān)系中的一個(gè)屬性。在本文中，側(cè)重于橫向分區(qū)，即每個(gè)服務(wù)器包含所有的屬性，但僅存儲(chǔ)所有屬性中的一個(gè)子集。文獻(xiàn)[7]提出了分布式環(huán)境中skyline查詢計(jì)算的最小邊界區(qū)域法（MBRs），分別計(jì)算每個(gè)服務(wù)器上存儲(chǔ)的數(shù)據(jù)，根據(jù)所有服務(wù)器的計(jì)算結(jié)果最終得到最后的理想結(jié)果。文獻(xiàn)[8]中提出了反饋式skyline查詢算法（FDS），F(xiàn)DS算法有效降低了傳輸大量的非skyline點(diǎn)數(shù)據(jù)，節(jié)省了帶寬成本。但是有些skyline點(diǎn)數(shù)據(jù)總是需要重復(fù)去計(jì)算，因此會(huì)產(chǎn)生較長(zhǎng)的響應(yīng)時(shí)間。文獻(xiàn)[5]中提出了一種基于網(wǎng)格的分布式skyline查詢處理算法（AgiDS），該方法在分布式服務(wù)器中采用并行計(jì)算的方法，響應(yīng)時(shí)間較快。但是，如果本地服務(wù)器發(fā)送到查詢服務(wù)器（QS）的數(shù)據(jù)重疊，這種方法就不能有效地減少這些重疊數(shù)據(jù)的傳輸了，這些數(shù)據(jù)只需在本地服務(wù)器進(jìn)行skyline查詢計(jì)算處理，而不需要傳輸?shù)讲樵兎?wù)器（QS）進(jìn)行全局的skyline查詢計(jì)算處理。文獻(xiàn)[9]提出的算法同樣是基于網(wǎng)格的算法（MGDS），是在文獻(xiàn)[5]的基礎(chǔ)上提出的關(guān)于處理數(shù)據(jù)重疊的一種改進(jìn)算法，但文章中關(guān)于重疊數(shù)據(jù)的處理算法隨意性太大，不同的人對(duì)重疊數(shù)據(jù)進(jìn)行處理的結(jié)果不同，而且結(jié)果可能相差很遠(yuǎn)。

3 二分式多層網(wǎng)格skyline查詢算法

3.1 基本思想

如前所述，如果發(fā)送到查詢服務(wù)器（QS）的本地服務(wù)器信息元組有重疊，方法AgiDS及MGDS都不能有效地減少重疊數(shù)據(jù)的傳輸，因此，提出了一種在分布式環(huán)境中的二分式多層網(wǎng)格skyline查詢算法（DMLG），假設(shè)每個(gè)服務(wù)器共享一個(gè)包含全部數(shù)據(jù)集的網(wǎng)格，給定一組分布式服務(wù)器S={S1，S2，…，Si}。每個(gè)服務(wù)器存儲(chǔ)全部數(shù)據(jù)集中的一部分?jǐn)?shù)據(jù)元組，并且每個(gè)服務(wù)器有能力針對(duì)自己存儲(chǔ)的數(shù)據(jù)元組進(jìn)行本地的skyline查詢計(jì)算，用戶發(fā)起skyline查詢的服務(wù)器稱做查詢服務(wù)器（Query Server，QS）。為了有效地對(duì)skyline查詢結(jié)果進(jìn)行評(píng)估，本文所述方法定義了在二維空間中，各單元格由每個(gè)單元格的左下角坐標(biāo)唯一確定，即單元格Di坐標(biāo)=（左下角橫坐標(biāo)，左下角縱坐標(biāo)），在網(wǎng)格中各單元格之間有以下三種控制關(guān)系：

（1）單元格A控制單元格B：如果單元格A的坐標(biāo)小于單元格B的坐標(biāo)。

（2）單元格B控制單元格A：如果單元格B的坐標(biāo)小于單元格A的坐標(biāo)。

（3）單元格A與單元格B重疊：如果單元格A的坐標(biāo)等于單元格B的坐標(biāo)。

注：所謂單元格A的坐標(biāo)小于單元格B的坐標(biāo)，指單元格A的左下角橫坐標(biāo)或左下角縱坐標(biāo)小于B的左下角橫坐標(biāo)或左下角縱坐標(biāo)，即包含以下三種情況：

（1）單元格A與單元格B橫坐標(biāo)相等，單元格A的縱坐標(biāo)小于單元格B縱坐標(biāo)。

（2）單元格A與單元格B縱坐標(biāo)相等，單元格A的橫坐標(biāo)小于單元格B橫坐標(biāo)。

（3）單元格A的橫坐標(biāo)和縱坐標(biāo)都小于單元格B的橫坐標(biāo)和縱坐標(biāo)。

如果單元格B被單元格A控制，就意味著單元格B中的所有數(shù)據(jù)元組都被單元格A中的任意一個(gè)數(shù)據(jù)元組所控制。定義包含skyline數(shù)據(jù)點(diǎn)的數(shù)據(jù)元組為本地skyline，如圖2深色區(qū)域所示。如果本地局部skyline在不同的服務(wù)器上發(fā)生重疊，定義這些重疊的數(shù)據(jù)元組為本地重疊skyline，如圖2中的單元格A和單元格B。在所述的二分式多層網(wǎng)格skyline查詢算法中，將本地重疊skyline包含的數(shù)據(jù)按重疊程度降序排列，將重疊程度在序列前半部分的重疊本地skyline定義為高度重疊本地skyline，如圖2中的單元格A和單元格B等。

圖2 DMLG算法的處理過程

3.2 DMLG算法的處理過程

DMLG的處理過程分為三個(gè)基本步驟：計(jì)劃，分析，執(zhí)行。在計(jì)劃的開始階段，skyline查詢首先由查詢服務(wù)器（QS）發(fā)起，各個(gè)服務(wù)器收到skyline查詢要求后，就利用當(dāng)前的網(wǎng)格算法計(jì)算它本地的局部skyline。然后查詢服務(wù)器聯(lián)絡(luò)各個(gè)連接的服務(wù)器，得到每個(gè)服務(wù)器上的局部skyline結(jié)果信息。分析階段，在查詢服務(wù)器中分析接收到的單元格內(nèi)數(shù)據(jù)，并對(duì)全局skyline作出評(píng)估，如果在所連接的服務(wù)器中出現(xiàn)了高度重疊局部skyline，則處理的方法是把它們放大到一個(gè)更高一層的網(wǎng)格。如圖2所示，在服務(wù)器S1和S2中，單元格A都是高度重疊的局部skyline，則會(huì)被轉(zhuǎn)移到更高一層的網(wǎng)格中去處理，而且單元格A中的數(shù)據(jù)點(diǎn)的管理和計(jì)算都是在它所在的高層網(wǎng)格中進(jìn)行的。然后，查詢服務(wù)器（QS）收集高層網(wǎng)格的當(dāng)?shù)鼐植縮kyline，并計(jì)算到全局skyline。如果在高一層的網(wǎng)格中還是有高度重疊本地skyline發(fā)生，則再把它放大到更高一層去處理。注意到圖2中，雖然單元格C在服務(wù)器S1和單元格D在服務(wù)器S2中也是本地skyline重疊的，但它卻不轉(zhuǎn)移到更高一層的網(wǎng)格中去處理，這是因?yàn)樵趩卧馛和單元格D中只有很少的數(shù)據(jù)，在低層中處理這些數(shù)據(jù)比在高層網(wǎng)格中處理更有效率。在執(zhí)行階段。存在于每個(gè)服務(wù)器的全局skyline數(shù)據(jù)點(diǎn)進(jìn)行最終的全局skyline計(jì)算。至此，由于大多數(shù)不必要的本地skyline數(shù)據(jù)點(diǎn)被過濾掉，該方法大大減少了信息的交換和處理時(shí)間。

為了更形象地理解所述方法，舉一個(gè)DMLG的例子，如圖2描述的一樣，假設(shè)每個(gè)服務(wù)器都有一個(gè)二維的數(shù)據(jù)集，網(wǎng)格是由3×3的單元格組成的。

在計(jì)劃階段，服務(wù)器S1中的單元格A，B，C和服務(wù)器S2中的單元格A，B，D被作為本地skyline被發(fā)送到查詢服務(wù)器進(jìn)行計(jì)算。分析階段，在查詢服務(wù)器中除去那些被控制的本地skyline。因?yàn)閱卧馎是高度重疊的區(qū)域skyline，所以它需要被放大到更高一層的網(wǎng)格中處理，單元格A中的數(shù)據(jù)也是在高一層的網(wǎng)格中處理的，在服務(wù)器S1和S2中分別各自計(jì)算本地高一層網(wǎng)格A-1，A-2，A-3，A-4，A-5和A-6的skyline。查詢服務(wù)器（QS）收集高層網(wǎng)格的本地skyline，并計(jì)算入全局skyline。由于服務(wù)器S1中的單元格A-3和服務(wù)器S2中的單元格A-5，A-6被服務(wù)器S1中的單元格A-1，A-2和服務(wù)器S2中的單元格A-4所控制，所以不屬于全局區(qū)域skyline。因此，在這個(gè)例子中，屬于全局區(qū)域skyline的單元格有：服務(wù)器S1網(wǎng)格中的單元格A，C，A-1，A-2及服務(wù)器S2網(wǎng)格中的單元格A，D，A-4。在執(zhí)行階段，只有這些單元格中的本地skyline數(shù)據(jù)被發(fā)送到查詢服務(wù)器進(jìn)行最后的全局skyline計(jì)算。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)描述

在這一節(jié)中，將介紹所述方法的性能，實(shí)驗(yàn)與文獻(xiàn)[4]所述方法MGDS和傳統(tǒng)方法作對(duì)比。表1顯示為實(shí)驗(yàn)的參數(shù)。

表1 實(shí)驗(yàn)的參數(shù)

在這個(gè)實(shí)驗(yàn)中，要用到兩種用于skyline算法測(cè)試的數(shù)據(jù)分布類型用來判定skyline計(jì)算方法的有效性，分別是反相關(guān)數(shù)據(jù)集和獨(dú)立數(shù)據(jù)集。在獨(dú)立數(shù)據(jù)集中，各個(gè)維度在取值上互不相關(guān)。在反相關(guān)數(shù)據(jù)集中，由于各維度的數(shù)值之間是反相關(guān)的關(guān)系，任意一個(gè)數(shù)據(jù)點(diǎn)在某個(gè)維度上數(shù)值很高，則會(huì)在另外一個(gè)維度上數(shù)值較低。

4.2 實(shí)驗(yàn)結(jié)果

設(shè)定所有分布式服務(wù)器都相互連接，并且每個(gè)服務(wù)器擁有相等數(shù)量的數(shù)據(jù)點(diǎn)，每個(gè)服務(wù)器中的數(shù)據(jù)點(diǎn)分散在整個(gè)網(wǎng)格的30%范圍內(nèi)。第一個(gè)實(shí)驗(yàn)，測(cè)試的性能是在網(wǎng)絡(luò)上傳輸?shù)目倲?shù)據(jù)量。研究的方法是在各個(gè)服務(wù)器上改變數(shù)據(jù)元組的數(shù)量，大小為從10×103逐漸到200×103，數(shù)據(jù)的維度設(shè)定為2維。圖3的結(jié)果顯示DMLG方法比MGDS和傳統(tǒng)方法都要好，這是因?yàn)榉莝kyline的數(shù)據(jù)點(diǎn)被這種二分式多層網(wǎng)格機(jī)制過濾掉了，從而減少了總的數(shù)據(jù)傳輸量。

圖3 不同數(shù)據(jù)大小的數(shù)據(jù)總傳輸量

圖4顯示的是三種方法根據(jù)不同數(shù)據(jù)大小所產(chǎn)生的響應(yīng)時(shí)間。在這個(gè)實(shí)驗(yàn)中，數(shù)據(jù)的維數(shù)同樣設(shè)定為2維，數(shù)據(jù)的大小范圍為10×103～200×103。從圖所示結(jié)果可以看到，隨著數(shù)據(jù)元組的增加響應(yīng)時(shí)間急劇上升，這是因?yàn)殡S著數(shù)據(jù)的增加，需要更高的處理成本，從而延長(zhǎng)了處理的時(shí)間。不管是對(duì)反相關(guān)數(shù)據(jù)集還是獨(dú)立數(shù)據(jù)集，DMLG方法的響應(yīng)時(shí)間比傳統(tǒng)方法和MGDS方法都要少，這是因?yàn)檫@種方法處理的數(shù)據(jù)比起另兩種方法都減少了很多。

圖4 不同數(shù)據(jù)大小的響應(yīng)時(shí)間

圖5所示為根據(jù)數(shù)據(jù)不同維數(shù)三種方法的響應(yīng)時(shí)間對(duì)比。在這個(gè)實(shí)驗(yàn)中，數(shù)據(jù)大小設(shè)定為10 000，在每個(gè)服務(wù)器上，逐漸增加數(shù)據(jù)集的維度并分別測(cè)定結(jié)果。從圖中可以看到，隨著維度的增加MGDS方法和傳統(tǒng)方法響應(yīng)的時(shí)間比DMLG方法增加得更快。這是因?yàn)殡S著維度的增加前兩種方法需要處理數(shù)據(jù)增加越來越快。

圖5 不同維數(shù)的響應(yīng)時(shí)間

5 結(jié)論與展望

本文研究了水平分區(qū)數(shù)據(jù)集的skyline查詢計(jì)算，由于相關(guān)的數(shù)據(jù)分散在幾個(gè)不同的服務(wù)器上，因此分布式環(huán)境中的skyline查詢，需要在各個(gè)連接的分布式服務(wù)器中收集大量的數(shù)據(jù)，本文所提方法DMLG利用多層網(wǎng)格的方法，借鑒二分法來處理分布式數(shù)據(jù)，這樣在發(fā)送到查詢服務(wù)器進(jìn)行最終全局skyline計(jì)算之前可以過濾掉許多不必要的本地非skyline數(shù)據(jù)，從而提高了查詢效率。實(shí)驗(yàn)結(jié)果表明所述方法比現(xiàn)有方法的效果要好。

將來比較重要和感興趣的后續(xù)工作包括：如何進(jìn)一步在進(jìn)行最終全局skyline計(jì)算之前可以過濾掉更多的本地非skyline數(shù)據(jù)，以及如何采用更優(yōu)秀的方法降低查詢的時(shí)間和提高查詢效率。

[1]Borzonyi S，Kossmann D，Stocker K.The skyline operator[C]// 17th International Conference on Data Engineering.Heidelberg：ICDE Press，2001：421-430.

[2]Chomicki J，Godfrey P，Gryz J.Skyline with presorting[C]// Proc of ICDE，2003：717-816.

[3]Kossmann D，Ramsak F，Rost S.Shooting stars in the sky：an online algorithm for skyline queries[C]//Proc of VLDB，2002：275-286.

[4]Papadias D，Tao Y，F(xiàn)u G，et al.An optimal and progressive algorithm for skyline queries[C]//Proc of Sigmod，2003：467-478.

[5]Rocha-Junior J B，Vlachou A，Doulkeridis C，et al.AGiDS：a grid-based strategy for distributed skyline query processing[C]// Second International Conference on Data Management in Grid and Peer to Peer Systems，Globe 2009，Linz，2009：12-23.

[6]Balke W T，Güntzer U，Zheng J X.Efficient distributed skylining for web information systems[C]//Hwang J，Christodoulakis S，Plexousakis D，et al.LNCS 2992，EDBT 2004，2004：256-273.

[7]Cui B，Lu H，Xu Q，et al.Parallel distributed processing of constrained skyline queries by filtering[C]//24th International Conference on Data Engineering，ICDE 2008，Cancun，2008：546-555.

[8]Zhu L，Tao Y，Zhou S.Distributed skyline retrieval with low bandwidth consumption[J].TKDE，2009，21：384-400.

[9]Li He，Jang Sumin，Yoo J.An efficient multi-layer grid method for Skyline queries in distributed environments[C]//LNCS 6637：DASFAA Workshops，2011：112-119.

[10]Zhu Lin，Guan Jihong，Zhou Shuigeng.Skyline computation：survey[J].Computer Engineering and Applications，2008，44（6）：160-165.

[11]Chan C Y，Jagadish H V，Tan K L，et al.Finding k-dominant skylines in high dimensional space[C]//Proc of SIGMOD，2006：503-514.

[12]Chan C Y，Eng P K，Tan K L.Stratified computation of skylines with partially ordered domains[C]//Proc of SIGMOD，2005：203-214.

[13]Tao Y，Papadias D.Maintaining sliding window skylines on data streams[J].IEEE Trans on KDE，2006，18（2）：377-391.

DING Riqiang

College of Information Science and Technology,Bohai University,Jinzhou,Liaoning 121000,China

In recent years,the skyline query has

more and more attention.This is because of its importance in many applications involving database visualization multi-criteria decision making,data mining and so on.Most of the previous works have put their attention on processing skyline queries on centralized data sets which is called centralized skyline query,and many research results have got.However,the reality is that the related data practically scatter at several different servers.The skyline query computation needs to gather a lot of data from the connected servers in distributed environment.The existing methods for distributed skyline query computation have two problems:firstly,their processing time for a skyline query is slow;secondly,they transfer many unnecessary data among servers in the network.This paper proposes a Dichotomous Multi-Layer Grid method（DMLG）.The proposed method based on the grid mechanism uses the dichotomy to minimize the unnecessary transferred data.Experiments based on different data sets show that this proposed method is better than the existing methods.

skyline query;distributed skyline query;distributed data;dichotomous multi-layer grid

skyline計(jì)算在數(shù)據(jù)挖掘、多標(biāo)準(zhǔn)決策和數(shù)據(jù)庫可視化等領(lǐng)域有著非常重要的作用，這些年已經(jīng)得到了廣泛的關(guān)注，以往對(duì)于skyline查詢的研究大多集中在處理集中的數(shù)據(jù)集上，即集中式skyline查詢，已經(jīng)得到了很多的研究成果。然而，實(shí)際情況是：相關(guān)數(shù)據(jù)幾乎分散在幾個(gè)不同的服務(wù)器上，因此在分布式環(huán)境中的skyline查詢計(jì)算需要從各個(gè)服務(wù)器收集大量的數(shù)據(jù)；現(xiàn)有的在分布式環(huán)境中的skyline查詢方法有兩個(gè)主要問題：一是skyline查詢的處理時(shí)間較慢；二是在網(wǎng)絡(luò)中服務(wù)器之間傳輸了很多不必要的重疊數(shù)據(jù)。提出了一種二分式多層網(wǎng)格法（DMLG），可以有效地處理在分布式環(huán)境中的skyline查詢。該方法利用網(wǎng)格的方法，借鑒二分法，最大限度地減少了不必要的重疊數(shù)據(jù)傳輸，基于不同的數(shù)據(jù)集的實(shí)驗(yàn)表明，這種方法優(yōu)于現(xiàn)有的方法。

skyline查詢；分布式skyline查詢；分布式的數(shù)據(jù)；二分式網(wǎng)格法

A

TP311

10.3778/j.issn.1002-8331.1203-0083

DING Riqiang.Dichotomous multi-layer grid method for skyline query in distributed computing environments.Computer Engineering and Applications,2013,49（18）：116-119.

遼寧省教育廳項(xiàng)目（No.L2010006）。

丁日強(qiáng)（1987—），男，碩士生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘技術(shù)，skyline計(jì)算。E-mail：drq211314@163.com

2012-03-05

2012-07-09

1002-8331（2013）18-0116-04