王　寧，曲海鵬，范　令

(中國海洋大學(xué)信息科學(xué)與工程學(xué)院， 山東 青島 266100)

?

一種分布式環(huán)境下高效查詢算法?

王寧，曲海鵬??，范令

(中國海洋大學(xué)信息科學(xué)與工程學(xué)院， 山東 青島 266100)

摘要：很多交互系統(tǒng)需要實(shí)時(shí)返回潛在的數(shù)據(jù)空間中最重要的前k條記錄，即為top-k查詢。當(dāng)今大數(shù)據(jù)時(shí)代，面對海量更加復(fù)雜的數(shù)據(jù)，輸出這種top-k記錄是一個(gè)非常具有挑戰(zhàn)性的問題。傳統(tǒng)的方案主要采用基于閾值的方法，然而對分布式系統(tǒng)來說，這些方法是比較耗時(shí)的，并且需要巨大的通信量。隨著網(wǎng)絡(luò)流量的增加，這些問題會(huì)變得無法解決。本文提出了一種新穎的top-k算法PCMRA(Data Partitioning and COIT Indexing Top-k query Algorithm based on MapReduce)。該解決方案構(gòu)造了預(yù)處理結(jié)構(gòu)COIT(候選對象索引表)，并采用數(shù)據(jù)分割策略和并行編程框架MapReduce，一輪通信就可以完成top-k查詢。此外本文還對算法給出了正確性證明和理論分析，并且實(shí)驗(yàn)表明該算法僅需要較小的空間開銷和較短的時(shí)間代價(jià)，即可篩選出較少的候選對象，大幅度節(jié)約了計(jì)算和通信資源，并且算法具有良好的可擴(kuò)展性。

關(guān)鍵詞：top-k查詢；COIT；數(shù)據(jù)分割； MapReduce

WANG Ning, QU Hai-Peng, FAN Ling. PCMRA: An efficient top-kalgorithm in distributed environment[J]. Periodical of Ocean University of China, 2016, 46(2): 138-145.

當(dāng)今大數(shù)據(jù)時(shí)代，數(shù)據(jù)不僅數(shù)量大，而且類型更加復(fù)雜，這導(dǎo)致了對數(shù)據(jù)處理的需求越來越高[1]。傳統(tǒng)的算法和數(shù)據(jù)庫系統(tǒng)已經(jīng)難以有效應(yīng)對，因此大數(shù)據(jù)快速查詢算法的研究成為熱點(diǎn)，排名查詢就是復(fù)雜查詢中一種。

排名查詢也被稱為top-k查詢，它為高效搜索問題提供了解決方案。top-k查詢只檢索k個(gè)最符合用戶需求的對象，從而避免計(jì)算、存儲(chǔ)大量的結(jié)果集。在傳統(tǒng)的集中式數(shù)據(jù)庫，分布式數(shù)據(jù)庫，以及大數(shù)據(jù)環(huán)境下，top-k查詢都已受到廣泛的重視，在這些應(yīng)用場景中，只計(jì)算輸出k個(gè)“最好”的結(jié)果就已經(jīng)足夠了。如有許多應(yīng)用，如網(wǎng)絡(luò)搜索，信息檢索，多媒體數(shù)據(jù)庫，數(shù)字圖書館，數(shù)據(jù)挖掘和推薦系統(tǒng)，只需要查詢前k個(gè)最好合乎要求的記錄[2]。

對于確定數(shù)據(jù)庫而言，根據(jù)數(shù)據(jù)庫的類型又分為兩大類。對于集中式數(shù)據(jù)庫，學(xué)術(shù)界為解決top-k查詢問題已經(jīng)做了很多工作[3]，而對于分布式數(shù)據(jù)庫，這個(gè)問題一直沒能得到很好的解決。根據(jù)數(shù)據(jù)劃分策略，top-k查詢又可以分為兩類[4]：一類數(shù)據(jù)是水平劃分的，這和本文所研究的應(yīng)用場景是完全不同的。另一類數(shù)據(jù)是垂直劃分的。對于這類top-k查詢，大多解決方案主要采用基于閾值的方法。TPUT[5]和Klee[6]算法就是這類算法的典型代表。這類算法是從集中式數(shù)據(jù)庫的算法發(fā)展來的，主要針對單一數(shù)據(jù)庫的，沒有考慮分布式的環(huán)境，盡管改進(jìn)，但是仍需要與服務(wù)器幾輪往返開銷才能完成查詢[7]，比較費(fèi)時(shí)，需要大量的通信。隨著網(wǎng)絡(luò)通信量的增加，top-k查詢將更加難以處理。

此外，近年來，由于在很多新興的應(yīng)用，如傳感器網(wǎng)絡(luò)，基于位置的服務(wù)，以及數(shù)據(jù)集成等應(yīng)用領(lǐng)域管理的信息往往是不確定的，為了處理數(shù)據(jù)的不確定性，概率數(shù)據(jù)庫被廣泛研究。隨之概率數(shù)據(jù)庫的top-k查詢問題也吸引了廣泛的研究興趣。在定義不確定型數(shù)據(jù)模型的基礎(chǔ)上，多種可能世界語義的top-k查詢模型已經(jīng)提出，包括U-Topk[9],U-kRanks[9],PT-k[10],Gobal-topk[11],以及Expected Rank queries[12]等，相應(yīng)的算法也被大量的研究。

本文為了提高算法的并行度，引入了計(jì)算模型MapReduce[8]。MapReduce是一個(gè)并行編程模型，它主要是針對大規(guī)模數(shù)據(jù)。它為用戶提供2個(gè)接口，方便用戶編寫一些自定義的代碼來處理大規(guī)模數(shù)據(jù)。

為了可以快速、準(zhǔn)確地完成top-k查詢，本文針對確定數(shù)據(jù)庫提出了一種高效的算法PCMRA。該算法需要預(yù)先構(gòu)建候選對象索引表COIT，top-k查詢的k值一般比較小，因此算法只需要維護(hù)有限的COIT記錄，就可以完成絕大多數(shù)top-k查詢。有限的數(shù)據(jù)記錄節(jié)約了數(shù)據(jù)構(gòu)建的成本以及占有的空間。數(shù)據(jù)一般分布在網(wǎng)絡(luò)中不同的節(jié)點(diǎn)，并且通常每個(gè)服務(wù)器中只儲(chǔ)存著一個(gè)或幾個(gè)屬性，而top-k查詢涉及到同一個(gè)對象的多個(gè)屬性的綜合得分，這就需要不止一個(gè)服務(wù)器的參與才能完成計(jì)算。本文采用數(shù)據(jù)劃分策略，減少了節(jié)點(diǎn)間的通信開銷，這就使算法具有很高的可擴(kuò)展性，隨著數(shù)據(jù)量的增加，這種優(yōu)勢將更加明顯。通過使用預(yù)構(gòu)建數(shù)據(jù)結(jié)構(gòu)COIT，我們的算法首先獲取候選id集合，然后根據(jù)數(shù)據(jù)劃分策略對候選id集合進(jìn)行分組。在得到分組后的id集合后，借助并行編程模型MapReduce的開源實(shí)現(xiàn)平臺(tái)Hadoop，只需一輪往返通信就可以完成top-k查詢。

1算法介紹

1.1 問題描述

top-k查詢：給定一個(gè)表T和一個(gè)單調(diào)的排名函數(shù)F，top-k查詢返回表T的一個(gè)包含k條記錄的子集R(k≤|T|))，滿足條件?ti∈R，?tj∈[T-R]，則F(ti)≥F(tj)。表的關(guān)系模式為T(ID，A1，A2，……，Am)，表T中元組tj的各屬性Ai都對應(yīng)一個(gè)得分值，記為Tj.bsi。排名函數(shù)F=∑wi×Tj.bsi是單調(diào)的，即對于?i，若存在1≤i≤m，xi≤yi，則F(x1，……，xm)≤F(y1，……，ym)，其中wi是對應(yīng)屬性Ai的權(quán)重，并且各屬性權(quán)重和為1，即∑wi=1。

1.2 預(yù)處理結(jié)構(gòu)

在收到top-k查詢之前，為了實(shí)現(xiàn)算法，需要預(yù)先建立數(shù)據(jù)結(jié)構(gòu)候選對象索引表COIT。COIT表是一種全局索引表，從中可以方便的查到各個(gè)k值以及各屬性組合對應(yīng)top-k查詢的候選id集合，借助COIT來可以快速的完成排名查詢。

全局索引表(COIT)：處理的數(shù)據(jù)對象是分布在不同數(shù)據(jù)源上的，每個(gè)數(shù)據(jù)源都是可以轉(zhuǎn)換或者提取出一個(gè)或者少數(shù)幾個(gè)關(guān)系模式R(O，A)，O為對象的鍵，如id等能唯一標(biāo)識對象的屬性列，A為該模式對應(yīng)屬性的得分，每個(gè)數(shù)據(jù)源都是按照屬性A得分降序排列的。如果可以提取到m個(gè)這樣的關(guān)系模式，我們可以假設(shè)多源數(shù)據(jù)的全部屬性可以組成一個(gè)大的虛擬的關(guān)系模式R’(O，A1，A2，……，Am)，Ai分別對應(yīng)屬性i的得分。

每個(gè)節(jié)點(diǎn)都需要建立一個(gè)id索引，記為Li，其中i∈(1，m)，該id索引是按照相關(guān)屬性的得分值降序排列的。索引Li的長度是可配置的。top-k查詢的k值一般較小，所以為了減少維護(hù)索引的空間代價(jià)和處理開銷，提高效率，設(shè)置了索引Li只有有限的記錄。索引Li的長度可根據(jù)實(shí)際應(yīng)用場景進(jìn)行設(shè)置。

每個(gè)數(shù)據(jù)源節(jié)點(diǎn)都將把各自的索引Li發(fā)送給全局節(jié)點(diǎn)，全局節(jié)點(diǎn)將根據(jù)所有屬性的索引建立全局的COIT。COIT包含了id以及在所在屬性列的排名，表中每一行形式如下(id，rank inL1，rank inL2……rank inLm) 。對于每一條記錄，它包括id和對象在所有節(jié)點(diǎn)的屬性排名，表1是多源數(shù)據(jù)庫索引一個(gè)實(shí)例，這一實(shí)例包括4列索引，各有5個(gè)元組，根據(jù)這一索引，按照COIT表構(gòu)建方法，建立COIT表如表2所示。

表1　多源數(shù)據(jù)索引實(shí)例

表2　COIT表

1.2.1 建立COIT表的步驟

(1)多數(shù)據(jù)源節(jié)點(diǎn)獲取按相關(guān)屬性降序排列的id索引列Li，初始化COIT表，COIT表中每條記錄形式如下(id，rank inL1，rank inL2……rank inLm)。

(2)逐行并行順序訪問m列id索引列，對讀取到的索引列Li的id，若該id已經(jīng)存在于COIT表中，則更新該id新讀到的排名rank；若訪問到的id不存在于COIT表中，則在COIT表末尾為該id新建一條記錄，并將排名rank記錄在相應(yīng)的列。

(3)順序訪問COIT表，對沒有排名信息的位置填入U(xiǎn)NDEF，代表該id在該列的排名rank暫時(shí)沒有讀到。

1.2.2 建立COIT表的偽代碼

算法1.建立COIT

Retrieve L1，L2，……,Lm

COIT[ ][ ] coit

Initialize coit

for i = 1 to the length of Li do

for j = 1 to m do

read current id

if (id is in coit)

//更新id在j個(gè)位置的排名為i；

updateCOIT(coit, id, j，i)

else

//在COIT表插入新id，并更新id

在j個(gè)位置的排名為i；

insertCOIT(coit, id, j，i)

end for

end for

fori = 1 to the length of COIT do

for j = 1 to m do

if (id rank is empty)

//更新id在j個(gè)位置的排名為UNDEF；

updateCOIT(coit, id,j，UNDEF)

end for

end for

return COIT

1.2.3 建立COIT表的流程圖

COIT表的建立流程見圖 1。

1.3 數(shù)據(jù)分割策略

算法處理的數(shù)據(jù)來自于不同源數(shù)據(jù)，每個(gè)數(shù)據(jù)源可能包含對象的一個(gè)或者少數(shù)幾個(gè)屬性信息，這些數(shù)據(jù)可以看做是根據(jù)不同屬性垂直分布在不同節(jié)點(diǎn)的。top-k查詢涉及到對象的多個(gè)屬性的綜合得分值，而這些屬性數(shù)據(jù)一般來說分散在網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)，如果直接查詢，通信的代價(jià)將會(huì)非常高。

為了降低節(jié)點(diǎn)間通信代價(jià)，在查詢處理之前，需要將這些不同源數(shù)據(jù)進(jìn)行預(yù)處理和劃分，使相同的對象劃分到相同的分組。假設(shè)id是區(qū)分對象的標(biāo)示符，則對象id被當(dāng)做劃分?jǐn)?shù)據(jù)的標(biāo)準(zhǔn)；數(shù)據(jù)源被分割成的子數(shù)據(jù)組的個(gè)數(shù)與數(shù)據(jù)處理的并行度Pn一致。引言中介紹了本算法采用的MapReduce這一并行處理模型，Pn的值取決于MapReduce這一并行編程模型。源數(shù)據(jù)的元組被分割到哪個(gè)子數(shù)據(jù)組取決于數(shù)據(jù)分割方法，本算法采用了簡單的hash函數(shù)映射的方法，將對象的id對N取模加1即得到子數(shù)據(jù)組的序號group.num，即

group.num=(object.id modN)+1。

(1)

圖1　COIT表的建立流程圖

這種分割函數(shù)簡單方便，每個(gè)對象都能被映射到唯一的子數(shù)據(jù)組，而且由于對象的id一般是連續(xù)遞增的，采用這種數(shù)據(jù)分割函數(shù)，能比較均勻的將數(shù)據(jù)分割到各個(gè)子數(shù)據(jù)組。不同源數(shù)據(jù)采用的數(shù)據(jù)分割函數(shù)要相同，在Pn和hash函數(shù)相同的條件下，可以保證不同源數(shù)據(jù)中id相同的對象被劃分到子序號相同的子數(shù)據(jù)組。這樣節(jié)點(diǎn)之間的通信量大幅度減少，以此來減少top-k查詢時(shí)節(jié)點(diǎn)間的通信代價(jià)。

1.4 PCMRA算法

本節(jié)介紹算法PCMRA的原理，收到top-k查詢之后，首先利用預(yù)先構(gòu)建的COIT，得到候選id集合，然后根據(jù)數(shù)據(jù)映射規(guī)則，將分組的id集合發(fā)送到相應(yīng)的節(jié)點(diǎn)，最后，由Hadoop平臺(tái)計(jì)算輸出整體的top-k查詢結(jié)果。具體算法細(xì)節(jié)步驟如下：

(1)top-k查詢解析。當(dāng)接收到top-k查詢時(shí)，首先根據(jù)查詢請求進(jìn)行解析，分析出查詢所涉及的屬性集合。

(2)獲取COIT相關(guān)排名表列。根據(jù)解析后的屬性集合，從COIT表中選取與這些屬性相關(guān)的排名表列。

(3)排名表列化簡。上一步已經(jīng)獲取所有id在查詢屬性列的所有排名，然而本文算法只關(guān)心這些屬性的排名范圍，即最大和最小排名，對于中間的排名可以不關(guān)心，因此可以對以上結(jié)果進(jìn)行化簡，只保留最大和最小排名。根據(jù)取到的相關(guān)的表列，逐行掃描，只保留每個(gè)id對象的最小排名和最大排名并分別定義為RankMin，RankMax。

(4)id集合排序。經(jīng)過以上處理得到id及其排名范圍，但是這些id可能是無序的，為了方便候選查詢，需要對這些id對象進(jìn)行排序。排序原則為，先根據(jù)RankMax升序排列，如果RankMax值相同，再按RankMin的升序排列。

(5)截止排名StopRank獲取。為了獲取候選id集合，需要事先獲取截止排名，定義為StopRank。StopRank跟隨k值的變化而變化的，根據(jù)查詢的k值，順序掃描排序后的id集合，當(dāng)讀到第k個(gè)id，得到該id的RankMax，表示當(dāng)并行順序訪問到第RankMax行時(shí)，第一次至少有k個(gè)對象全部屬性都已讀到。該RankMax值即為StopRank。

(6)候選id集合獲取。根據(jù)上述StopRank值，將所有RankMin不大于StopRank的id插入到候選id集合中。

(7)候選id集合分組。由于獲得的候選id集合是混亂的，我們需要按照數(shù)據(jù)分割策略對它們進(jìn)行分組和編號。數(shù)據(jù)是根據(jù)哈希函數(shù)來分割的，編號是按模取余來編號的。

(8)Hadoop并行計(jì)算和top-k結(jié)果輸出。為了提高算法的并行度，啟動(dòng)Hadoop完成結(jié)果top-k計(jì)算。輸入為分組并編號的原始數(shù)據(jù)和分組并編號的候選id集合。計(jì)算時(shí)，只需要根據(jù)原始數(shù)據(jù)的編號找到編號相同的候選id集合分組。只對包含在候選id集合的數(shù)據(jù)進(jìn)行計(jì)算。被分配到做map操作的worker節(jié)點(diǎn)，做map操作“map(id， wi×listi.value)”，被分配到做reduce操作的worker節(jié)點(diǎn)，做reduce操作“reduce(id， list ( w1×list1.value, ……,wm×listm.value))”，最終輸出最大的k個(gè)結(jié)果作為最終輸出。

1.4.1 PCMRA算法偽代碼

算法2. 獲取候選id分組

AttrColumn[]related_Attributes

COIT[] [] coit

COIT[] [] coit1

COIT[] [2] coit2

ID[] Id

ID[N][] IdGroup

int i,j,RankMin, RankMax,StopRank

coit = Establish COIT( )

//解析top-k查詢的相關(guān)屬性；

related_Attributes= parse(String sql)

//獲取COIT相關(guān)排名表列；

coit1 = retrieveCOIT(related_Attributes，coit)

for i = 1 to the length of coit1 do

for j=1 to the length of related_Attributes do

RankMin = read(coit1[i],1)

RankMax = read(coit1[i],1)

if (read(coit[i],j) > RankMax)

RankMax = read(coit1[i],j)

if(read(coit[i],j) < RankMax)

RankMin = read(coit1[i],j)

end for

insertCOIT(coit2, id, 1，RankMin)

updateCOIT(coit2, id, 2，RankMax)

end for

//排序，按RankMax升序排列，如過RankMax相同則按RankMin升序排列

sort(coit2)

//獲取StopRank值；

StopRank = (coit2[k],2)

//候選Id集合獲取

Id = retrieveIds(coit2, StopRank)

//候選Id集合分組

IdGroup = group(id,N)

return IdGroup

1.4.2 PCMRA算法流程圖

本文PCMRA算法的流程見圖2。

圖2　PCMRA算法流程圖

2理論分析

2.1 算法正確性證明

定理1對于任意一個(gè)k值和任意一個(gè)單調(diào)得分函數(shù)F，top-k結(jié)果集O是候選id集合X的子集。所有未出現(xiàn)在候選id集合X中的對象z，肯定不屬于top-k結(jié)果集O。

證明假設(shè)用集合A表示所有的id集合，用X表示對于確定k值和確定得分函數(shù)F的候選id集合，用集合Y表示集合A中除去集合X剩下對象集合，即A-X。我們需要證明top-k結(jié)果集O是候選id集合X的子集，而顯然候選id集合Y中對象個(gè)數(shù)是大于等于k的，因此不可能成為top-k結(jié)果集O的子集，因此只需要證明任何出現(xiàn)在集合Y中的對象z不屬于top-k的結(jié)果集O。假設(shè)，F(xiàn)函數(shù)涉及到m個(gè)屬性得分，而出現(xiàn)在集合Y中的對象z的m個(gè)屬性得分為x1,…,xm。

根據(jù)候選id的獲取方法，首先確定所有id的排名范圍，即最大排名RankMax和最小排名RankMin，假設(shè)對m個(gè)排序列做并行順序訪問，id的最大排名RankMax和最小排名RankMin，分別表示該id第一次被訪問的行數(shù)和最后一次被訪問的行數(shù)，也就是當(dāng)訪問到第RankMax行時(shí)，該對象的所有屬性得分都已經(jīng)被訪問到。然后對所有對象按照先按RankMax再按RankMin的升序排列，讀取第k個(gè)id的最大排名RankMax即為StopRank，也就是表示當(dāng)讀到第StopRank行時(shí)，有k個(gè)對象的所有屬性得分都已經(jīng)被讀到。最后取出所有最小排名RankMin小于StopRank的id放入候選id集合X，因?yàn)檫@些對象都曾經(jīng)出現(xiàn)在StopRank行之前。

已知而每個(gè)排序列是按照屬性得分的降序排列的，所以，顯然先被訪問到的得分要比后被訪問的得分高。假設(shè)所有屬性都被訪問對象中，第k大的對象p的屬性得分為x1,…,xm，顯然對于任何i，都有xm≤xm，又因?yàn)榈梅趾瘮?shù)F時(shí)單調(diào)增的，所以F(x1,…,xm)≤F(x1,…,xm,)，即對象集合Y中任意對象z得分肯定小于排名為k的對象得分，也就是說出現(xiàn)在集合Y中任何對象z都不屬于top-k結(jié)果集O。

2.2 算法分析

本節(jié)根據(jù)算法流程進(jìn)行詳細(xì)的理論分析。COIT記錄有P條記錄，候選屬性列有M個(gè)。

2.2.1時(shí)間復(fù)雜度按照算法詳細(xì)流程，收到top-k查詢處理之后對查詢進(jìn)行解析，得到k值和相關(guān)列，時(shí)間復(fù)雜度為O(1)；獲取排名表列，進(jìn)行化簡，將所有id掃描一遍即可完成，算法時(shí)間復(fù)雜度為O(P)；對id集合排序，排序時(shí)只需要對MaxRank較小的前k個(gè)對象排序即可，遍歷一遍所有id，時(shí)間復(fù)雜度為O(P)，前k個(gè)對象的排序，用插入排序法，時(shí)間復(fù)雜度為O(k2)；候選id集合獲取和分組時(shí)間復(fù)雜度都為O(P)，上述步驟都在內(nèi)存中可以完成，不需要I/O操作；最后Hadoop并行計(jì)算和top-k結(jié)果輸出即可，時(shí)間復(fù)雜度跟Hadoop平臺(tái)有關(guān)。除去Hadoop的計(jì)算時(shí)間，綜上，時(shí)間復(fù)雜度為O(P+k2)。

2.2.2 空間復(fù)雜度算法預(yù)先建立的數(shù)據(jù)結(jié)構(gòu)COIT只記錄有限條記錄，因此該空間開銷是比較小的。整個(gè)算法中，Master節(jié)點(diǎn)需要維護(hù)一個(gè)全局的COIT表，假設(shè)有M個(gè)屬性，對象id和M個(gè)屬性都為整數(shù)，占4個(gè)字節(jié)，則COIT表每條記錄占4(M+1)字節(jié)，整個(gè)COIT表占4(M+1)×P。在算法計(jì)算過程中，需要建立臨時(shí)候選id集合，每個(gè)id只保留RankMax和RankMin，所以每條記錄占12個(gè)字節(jié)，空間開銷為12P字節(jié)。對id集合排序過程中，需要維護(hù)前k條記錄，每條記錄只保留id和RankMax，占8k字節(jié)。綜上，空間開銷為O(MP+k)。

3實(shí)驗(yàn)分析

在本節(jié)中，通過實(shí)驗(yàn)來評估算法PCMRA。首先，介紹實(shí)驗(yàn)設(shè)計(jì)。然后是具體實(shí)驗(yàn)以及結(jié)果分析。

3.1 實(shí)驗(yàn)設(shè)計(jì)

3.1.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)在6臺(tái)32位Linux機(jī)器上運(yùn)行，每一臺(tái)處理器型號為奔騰G620，主頻2.60GHz的，內(nèi)存4GB，硬盤8G,操作系統(tǒng)為centos。這些機(jī)器都預(yù)先安裝并行數(shù)據(jù)處理引擎的Hadoop。這些機(jī)器與局域網(wǎng)連接起來，局域網(wǎng)網(wǎng)速為1000Mbps。算法用Java完成。

3.1.2 對比實(shí)驗(yàn)對比實(shí)驗(yàn)不采用預(yù)處理數(shù)據(jù)結(jié)構(gòu)COIT，用Hadoop平臺(tái)計(jì)算所有對象的得分，并排序得到前k個(gè)對象，本文稱該對比算法為Naive算法。

3.1.3 數(shù)據(jù)集均勻分布數(shù)據(jù)集。

3.1.4 實(shí)驗(yàn)參數(shù)元組數(shù)N，一共分為10組，取值分別為1k，2k，3k，4k，5k，6k，7k，8k，9k，10k,默認(rèn)取值為5k。

查詢結(jié)果數(shù)k，也分為10組，取值分別為10，20，30，40，50，60，70，80，90，100，默認(rèn)取值為50。

查詢屬性個(gè)數(shù)W，也分為10組，取值分別為1，2，3，4，5，6，7，8，9，10，默認(rèn)取值為5。

3.1.5 性能指標(biāo)運(yùn)行時(shí)間time：顯然算法運(yùn)行時(shí)間越短代表算法的性能越好。

候選元組比率Ratio：Ratio為本文自定義的參數(shù)，它是總的元組數(shù)N、查詢結(jié)果數(shù)K以及查詢屬性個(gè)數(shù)W的乘積與候選id個(gè)數(shù)Cn的比值的倒數(shù)的1000倍。容易看出，候選id個(gè)數(shù)Cn，隨著總的元組數(shù)N,查詢結(jié)果數(shù)K以及查詢屬性個(gè)數(shù)W的增加，其候選id個(gè)數(shù)顯然是增加的，顯然候選id個(gè)數(shù)Cn與以上3個(gè)因素是成正相關(guān)的。因此如果算法是線性可擴(kuò)展的，則隨著元組數(shù)N的線性增長，候選元組數(shù)也是線性增長的。倘若算法線性擴(kuò)展能力好，在總的元組數(shù)N、查詢結(jié)果數(shù)K以及查詢屬性個(gè)數(shù)W其中2個(gè)值固定，一個(gè)值線性增長的情況下，候選元組比率應(yīng)該Ratio是一常量，甚至是降低的。Ratio的計(jì)算公式如下：

(2)

3.1.6 查詢設(shè)定為了方便起見，查詢請求的各屬性權(quán)重設(shè)為wi=1/W,查詢屬性列選取COIT表中前W列屬性。

3.2 實(shí)驗(yàn)及結(jié)果分析

3.2.1 實(shí)驗(yàn)一：元組數(shù)N的影響設(shè)定k=50，W=5，實(shí)驗(yàn)一反映了PCMRA和Naive算法隨著元組數(shù)N的變化，算法的性能指標(biāo)的變化。圖3(a)表明隨著元組數(shù)從1k增加到10k，PCMRA算法候選元組比率Ratio從0.17左右降到大約0.03，并且在元組數(shù)為10k時(shí)，候選元組比率Ratio僅為0.03，根據(jù)公式計(jì)算，候選元組數(shù)Cn僅為總元組數(shù)的8%左右，篩選的不相關(guān)元組數(shù)能達(dá)到90%以上，并且由圖中趨勢推斷，隨著元組數(shù)的增加，候選元組比例仍在降低，而Naive算法一直穩(wěn)定在4。Ratio越低說明算法性能越好，說明PCMRA算法性能更優(yōu)，明顯具有更好的擴(kuò)展性。圖3(b)表明隨著元組數(shù)從1k遞增到10k，PCMRA算法運(yùn)行時(shí)間從24s增到27s，時(shí)間增加12.5%，而Naive算法從25s增加到34s，時(shí)間增加36%，顯然Naive算法比PCMRA算法運(yùn)行時(shí)間慢，并且增幅比為后者的將近3倍。由圖中趨勢看隨著元組數(shù)N的增加，這一差異將更加明顯，顯然PCMRA算法在時(shí)間性能上更好。

圖3　元組數(shù)N的影響

3.2.2 實(shí)驗(yàn)二：查詢結(jié)果數(shù)k的影響設(shè)定N=5k，W=5，實(shí)驗(yàn)二反映了PCMRA和Naive算法隨著查詢結(jié)果數(shù)k的變化，算法的性能指標(biāo)的變化。圖4(a)表明隨著查詢結(jié)果數(shù)從10逐漸增加到100，PCMRA算法候選元組比率Ratio從0.85降到0.45左右，雖然Naive算法候選元組比率Ratio從20降到2，降幅明顯，但是前者一直比后者低，并且前者比例也一直在降低。同實(shí)驗(yàn)一分析結(jié)果一致。圖4(b)表明隨著查詢結(jié)果數(shù)從10遞增到100，PCMRA算法運(yùn)行時(shí)間從24s增到25s，而Naive算法從25s增加到28s，2個(gè)算法時(shí)間增加都不明顯，但是PCMRA算法仍然比Naive算法運(yùn)行時(shí)間短，PCMRA算法在時(shí)間性能上仍然優(yōu)于Naive算法。

圖4　查詢結(jié)果數(shù)k的影響

3.2.3 實(shí)驗(yàn)三：查詢屬性個(gè)數(shù)W的影響設(shè)定k=50，N=5k，實(shí)驗(yàn)三反映了PCMRA和Naive算法隨著查詢屬性個(gè)數(shù)W的變化，算法的性能指標(biāo)的變化。圖5(a)表明查詢屬性從1個(gè)增加到10個(gè)，PCMRA算法候選元組比率Ratio比例一直在0.5左右，仍有不太明顯的降低趨勢，同實(shí)驗(yàn)二，Naive算法降幅明顯，但是仍然一直比PCMRA算法Ratio要高的多，因此分析結(jié)果同實(shí)驗(yàn)一一致。圖5(b)表明查詢屬性從1個(gè)增加到10個(gè)，PCMRA算法運(yùn)行時(shí)間從23s增到25s，而Naive算法從25s增加到30s，同實(shí)驗(yàn)二2個(gè)算法時(shí)間增加都不明顯，但是PCMRA算法仍然比Naive算法運(yùn)行時(shí)間短，PCMRA算法在時(shí)間性能上仍然優(yōu)于Naive算法。

圖5　查詢屬性個(gè)數(shù)W的影響

4結(jié)語

本文中，我們分析了當(dāng)今數(shù)據(jù)的發(fā)展趨勢，而現(xiàn)有算法比較耗時(shí)，并需要大量的通信。隨著網(wǎng)絡(luò)數(shù)據(jù)的增加，傳統(tǒng)的top-k算法更加難以處理這些問題。所以本文提出了一種分布式環(huán)境下top-k算法PCMRA。它僅需要較小的構(gòu)建代價(jià)和較少的空間開銷，就可以建立數(shù)據(jù)預(yù)處理結(jié)構(gòu)COIT。借助COIT，使用我們的數(shù)據(jù)分割策略，并采用并行編程模型MapReduce，我們的算法PCMRA只需要與服務(wù)器的一輪通信就可以完成top-k查詢。本文給出了算法正確性證明，并對算法的時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行分析。實(shí)驗(yàn)部分表明該算法僅涉及有效通信，并且運(yùn)行時(shí)間短，查詢結(jié)果準(zhǔn)確，可擴(kuò)展性好。這表明該算法在一定條件下優(yōu)于現(xiàn)有的算法。

本文算法設(shè)計(jì)針對大數(shù)據(jù)的應(yīng)用環(huán)境的確定數(shù)據(jù)庫，但是隨著數(shù)據(jù)的爆炸增長，數(shù)據(jù)的不確定性為top-k查詢問題帶來了很多困難，圍繞不確定型數(shù)據(jù)模型和可能世界語義的top-k查詢已經(jīng)引起了廣泛的關(guān)注。但可能世界語義的top-k查詢問題仍需要大量的研究。下一步，我們將本文的算法擴(kuò)展到不確定數(shù)據(jù)庫。首先定義基于多屬性綜合得分的可能世界語義的top-k查詢模型，然后針對此查詢，設(shè)計(jì)一種帶有預(yù)處理結(jié)構(gòu)的不確定數(shù)據(jù)庫上top-k查詢,并沿用數(shù)據(jù)分割和采用MapReduce并行編程的思路。

參考文獻(xiàn)：

[1]Lohr S. The Age of Big Data[J]. SR1, online: http: //www.nytimes.com/2012/02/12/sunday-review/big-datas-impact- in-the-world.html, 2012, 16(4): 10-15.

[2]Han X, Li J, Wang J, et al. TJJE: An efficient algorithm for top-k join on massive data[J]. Information Sciences An International Journal, 2013, 222(3): 362-383.

[3]Ronald Fagin, Amnon Lotem, Moni Naor. Optimal aggregation algorithms for middleware[J]. Journal of Computer and System Sciences， 2003: 102-113.

[4]Zhao K, Tao Y, Zhou S. Efficient top- k processing in large-scaled distributed environments[J]. Data & Knowledge Engineering, 2007, 63(2): 315-335.

[5]Cao Pei, Wang Zhe. Efficient Top-K Query Calculation in Distributed Networks[C].Newfoundland: PODC, 2004: 206-215.

[6]Michel S, Triantafillou P, Weikum G. KLEE: A Framework for Distributed Top-K Query Algorithms[J]. Vldb, 2005: 637-648.

[7]Chrysakis I, Chalkidis C, Plexousakis D. A Detailed Evaluation of Threshold Algorithms for Answering Top-k queries in Peer-to-Peer Networks[J]. 2010.

[8]Dean J, Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters.[J]. In Proceedings of Operating Systems Design and Implementation 2004, 51(1): 107-113.

[9]Soliman M A, Ilyas I F, Chen-Chuan Chang K. Top-k Query Processing in Uncertain Databases[C]//Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on. IEEE, 2007: 896-905.

[10]Hua M, Pei J, Zhang W, et al. Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach[C]. Florida: Computer Science Department, Florida State University, 2008: 673-686.

[11]Yi K, Li F, Kollios G, et al. Efficient processing of top-k queries in uncertain databases with x-relations.[J]. IEEE Transactions on Knowledge & Data Engineering, 2008, 20(12): 1669-1682.

[12]Cormode G, Li F, Yi K. Semantics of Ranking Queries for Probabilistic Data and Expected Ranks[C].Chicago: 2014 IEEE 30th International Conference on Data Engineering, 2009: 305-316.

責(zé)任編輯陳呈超

PCMRA: An Efficient Top-kAlgorithm in Distributed Environment

WANG Ning, QU Hai-Peng, FAN Ling

(College of Information Science and Engineering, Ocean University of China, Qingdao 266100, China)

Abstract：With the unceasing expansion size of the data and the increasing complexity of data types, human race has entered the era of big data. On the one hand, there is a sharp increase of the data provided from different areas and applications, on the other hand, the traditional data processing techniques can not cope with such a large-scale data, thus this situation brings serious challenges to the current data processing techniques. We are on a pressing demand to effectively dig out the beneficial information we need, thus we have to raise a faster and more effective query technique. Ranking queries, which is known as top-k query, is one of various complex data queries. It works by calculating the scores of all objects by an aggregation function, and then return the top-k objects with the highest scores. For many interactive systems, efficient Top-k query are very important. Top-k query problem also involves a lot of database processing technologies, including indexing and query optimization, etc. Top-k query is now attracting more and more attention for the broad use and the efficiency, so it is now a hot spot in research area, and it is also has very important theory value and the very extensive application prospects. This paper mainly researched on the corresponding top-k query algorithm for large-scale data, and then made some innovation. Finding the top-k best records among the potentially huge answer space in real time for many interactive systems, is a challenging issue today, for there is an increasing trend that more and more data needs to be processed. With the increase of network traffic, these problems will become unsolvable. Learning from the good features of the traditional top-k query processing technology and using parallel programming model - MapReduce, this paper proposes a novel top-k algorithm PCMRA(Data Partitioning and COIT Indexing Top-k query Algorithm based on MapReduce). Our solution develops a pre-construction algorithm to construct COIT (Candidate Objects Index Table), adopting a new strategy of data partitioning, completing the top-k query in one round by means of parallel programming model: MapReduce. The correctness proof and cost analysis of PCMRA are present in this paper. Experiments show that the algorithm only requires lower construction cost and less space overhead . A small number of candidate objects can be selected in a relatively short period of time, greatly saving computing and communication resources, and also the algorithm has good scalability.

Key words:top-k query; COIT; data partitionin; MapReduce; massive data

DOI：10.16441/j.cnki.hdxb.20140032

中圖法分類號：TP311

文獻(xiàn)標(biāo)志碼：A

文章編號：1672-5174(2016)02-138-08

作者簡介：王寧(1987-)，女，碩士生。E-mail：wangnynn@gmail.com??通訊作者： E-mail:quhaipeng@ouc.edu.cn

收稿日期：2014-03-05；

修訂日期：2014-10-09

基金項(xiàng)目：? 國家自然科學(xué)基金項(xiàng)目(60773057)；國家海洋局海洋公益項(xiàng)目(201105033)

引用格式：王寧， 曲海鵬， 范令. 一種分布式環(huán)境下高效查詢算法[J]. 中國海洋大學(xué)學(xué)報(bào)(自然科學(xué)版)， 2016, 46(2)： 138-145.

Supported by National Natural Science Foundation of China(60773057)；The State Oceanic Administration of Marine Public Welfare Projects(201105033)