一種海量分布式數(shù)據(jù)Top-k查詢算法＊

魏賢全，鄭洪源，丁秋林

（南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京210016）

1 引言

近年來，隨著云計(jì)算和數(shù)據(jù)密集型運(yùn)算領(lǐng)域迅速發(fā)展，數(shù)據(jù)處理規(guī)模不斷擴(kuò)大，為分布式環(huán)境下Top-k查詢帶來了新的挑戰(zhàn)，如何在海量分布式數(shù)據(jù)中實(shí)現(xiàn)Top-k查詢成為了研究的熱點(diǎn)。Top－k查詢是一種十分重要的查詢操作，廣泛應(yīng)用于網(wǎng)絡(luò)和系統(tǒng)監(jiān)控、證券分析、網(wǎng)絡(luò)日志分析等領(lǐng)域。這些應(yīng)用均產(chǎn)生了海量數(shù)據(jù)，這些數(shù)據(jù)通常分散在各地的網(wǎng)絡(luò)節(jié)點(diǎn)，Top-k查詢的目的是在大量的數(shù)據(jù)中找出用戶最為關(guān)心的k個(gè)值。例如，通過谷歌搜索“Top-k”，返回結(jié)果約有 3 680 000 000條。為了使用戶有良好的使用體驗(yàn)，搜索引擎系統(tǒng)需能夠快速地返回評(píng)分結(jié)果最高的前k個(gè)查詢結(jié)果。

目前，針對(duì)分布式數(shù)據(jù)的Top-k查詢存在多種算法，例如最被廣泛認(rèn)可的是TA（Threshold Algorithm）算法［1～3］，但是TA算法通常適用于集中式網(wǎng)絡(luò)，如傳統(tǒng)的針對(duì)數(shù)據(jù)庫的應(yīng)用程序。當(dāng)應(yīng)用于大型分布式網(wǎng)絡(luò)的時(shí)候，由于TA算法中數(shù)據(jù)交換的次數(shù)不能預(yù)先確定，往往會(huì)帶來大量的帶寬消耗。因此，第一個(gè)適用于分布式網(wǎng)絡(luò)環(huán)境并且擁有固定交換次數(shù)的算法 TPUT（Three-Phase Uniform-Threshold algorithm）［4］被 提 出。TPUT 算法在很大程度上減少了網(wǎng)絡(luò)的存取代價(jià)，但TPUT算法的效率是建立在假設(shè)各節(jié)點(diǎn)數(shù)據(jù)具有相同的分布性的基礎(chǔ)上，對(duì)于實(shí)際的分布式系統(tǒng)效率則可能較低。KLEE算法［4］給出了分布式環(huán)境下的Top-k算法的框架，它允許在效率和結(jié)果質(zhì)量之間做出權(quán)衡取舍，但是KLEE得到的僅僅是Top-k查詢的近似結(jié)果。文獻(xiàn)［5］給出了動(dòng)態(tài)分布式環(huán)境下的Top-k查詢計(jì)算方法，該算法主要從網(wǎng)絡(luò)拓?fù)涞慕嵌忍岣吡瞬樵兊男?，但沒有充分考慮各節(jié)點(diǎn)的數(shù)據(jù)分布，網(wǎng)絡(luò)傳輸總量仍然較高。文獻(xiàn)［6～8］討論了分布式環(huán)境下基于skyline的Top-k查詢以及傳感器網(wǎng)絡(luò)的Top-k查詢。文獻(xiàn)［9］對(duì) TPUT算法進(jìn)行了改進(jìn)，提出了 TPOR（Three-Phase Object-Ranking algorithm）和 HT（Hybrid-Threshold algorithm）算法。TPOR算法采用傳輸對(duì)象的排名取代傳輸對(duì)象的數(shù)值，在一定程度上避免了單一節(jié)點(diǎn)傳輸數(shù)據(jù)量過大的問題，但是若各節(jié)點(diǎn)排名相差較大時(shí)，效率比TPUT更差。HT算法結(jié)合了TPOR和TPUT兩種算法的優(yōu)點(diǎn)，但是由于沒有考慮數(shù)據(jù)分布情況以及存在閾值計(jì)算粗糙的缺點(diǎn)，應(yīng)用于實(shí)際情況時(shí)往往仍有很大的網(wǎng)絡(luò)消耗。

鑒于現(xiàn)有算法的不足，本文提出了適用于海量分布式數(shù)據(jù)的Top-k查詢新算法ECHT（Early－Clipping Histogram-Threshold algorithm）。該算法的主要優(yōu)勢(shì)有以下幾點(diǎn)：（1）采用改進(jìn)限定誤差直方圖描述各節(jié)點(diǎn)數(shù)據(jù)分布情況，改善了同類算法數(shù)據(jù)分布不均時(shí)Top-k查詢低效問題。（2）引入了早裁剪思想，在大量數(shù)據(jù)對(duì)傳輸之前，結(jié)合改進(jìn)限定誤差直方圖和數(shù)據(jù)排名提前進(jìn)行數(shù)據(jù)裁剪，從而大量減少網(wǎng)絡(luò)帶寬消耗。（3）改進(jìn)的閾值計(jì)算方法提高了閾值估算精度，進(jìn)一步降低了網(wǎng)絡(luò)帶寬消耗。實(shí)驗(yàn)表明，ECHT算法在網(wǎng)絡(luò)帶寬消耗和網(wǎng)絡(luò)響應(yīng)時(shí)間方面均優(yōu)于其他同類算法。

2 問題描述

分布式環(huán)境下Top-k查詢的定義如下：假設(shè)分布式網(wǎng)絡(luò)中有（m＋1）個(gè)節(jié)點(diǎn)，其中有一個(gè)中心節(jié)點(diǎn)N0和m 個(gè)節(jié)點(diǎn)N1，N2，…，Nm。N1，N2，…，Nm均和中心節(jié)點(diǎn)N0相連，每個(gè)節(jié)點(diǎn)Ni存儲(chǔ)的是形如 〈x，vi（x）〉的數(shù)據(jù)序列，其中x表示對(duì)象的標(biāo)識(shí)符，vi（x）表示對(duì)象x在節(jié)點(diǎn)Ni的屬性值，各節(jié)點(diǎn)按照vi（x）屬性值大小降序排列。每個(gè)節(jié)點(diǎn)的數(shù)據(jù)對(duì)象存在重疊但又不完全相同，如果對(duì)象y不出現(xiàn)在節(jié)點(diǎn)Ni，則定義vi（y）＝0。

假定所有對(duì)象的數(shù)據(jù)集為U ＝ ｛O1，O2，…，On｝，對(duì)于對(duì)象Oi，令vij（y）表示對(duì)象Oi在節(jié)點(diǎn)Nj的屬性值。令Vi為對(duì)象Oi在中心節(jié)點(diǎn)N0的聚集值，即對(duì)象Oi的評(píng)分。則：

其中，f通常是連續(xù)的嚴(yán)格單調(diào)函數(shù)。Top-k查詢的目標(biāo)就是返回所有對(duì)象中評(píng)分最高的k個(gè)對(duì)象作為查詢的結(jié)果，為了討論方便，本文采用聚集函數(shù)作為求和函數(shù)。

在分布式環(huán)境下，Top-k查詢的目標(biāo)是用最少的帶寬消耗查找出最高評(píng)分的k個(gè)對(duì)象，由于目前在實(shí)際的分布式網(wǎng)絡(luò)環(huán)境下，帶寬和傳輸速度相對(duì)于時(shí)間仍然是主要瓶頸，所以為了簡化問題的分析，假設(shè)在每個(gè)節(jié)點(diǎn)的計(jì)算成本可以忽略不計(jì)而節(jié)點(diǎn)間的通信開銷就是查詢響應(yīng)時(shí)間。因此，本文以網(wǎng)絡(luò)中傳輸〈object，Score〉對(duì)的數(shù)目作為算法表現(xiàn)的判別標(biāo)準(zhǔn)，因?yàn)槠湎牧私^大部分帶寬。

3 ECHT算法

本節(jié)主要介紹基于改進(jìn)限定誤差直方圖和早裁剪思想的Top-k查詢新算法ECHT，首先介紹數(shù)據(jù)分布的描述方法，給出改進(jìn)限定誤差直方圖形式化描述，設(shè)計(jì)直方圖信息的存儲(chǔ)結(jié)構(gòu)，并簡要說明選用改進(jìn)限定誤差直方圖描述數(shù)據(jù)分布的原因及優(yōu)勢(shì)；之后介紹早裁剪算法，簡要論證ECHT算法的查詢結(jié)果是Top-k查詢的準(zhǔn)確結(jié)果；最后給出了ECHT算法的詳細(xì)步驟。

3.1 改進(jìn)限定誤差直方圖

限定誤差直方圖［10］的相關(guān)定義如下：

設(shè)U ＝ ｛O1，O2，…，On｝是由n個(gè)對(duì)象組成的對(duì)象集，A ＝ ｛a1，a2，…，am｝是U 的屬性集，為了討論方便，假設(shè)A中每個(gè)元素的值域?yàn)檎麛?shù)，取值介于Min和Max之間（包含Min和Max）。節(jié)點(diǎn)Ni的數(shù)據(jù)存儲(chǔ)形式為數(shù)值對(duì)〈Oi，Ai〉。我們用二元組集合 T ＝ ｛〈a1，v1〉，〈a2，v2〉，…〈am，vm〉｝來表示對(duì)象的數(shù)值分布。這里，vi表示U中屬性值

T上的直方圖H定義如下：

定義2 （限定誤差為Const的直方圖）對(duì)直方圖H，Const是一個(gè)給定的常數(shù)，作為額定誤差。對(duì)任意的a和b，a∈A，b∈A，a≤b，對(duì)范圍查詢t，t.A≥a∧t.A≤b，有｜r－r′｜≤Const，這里的r和r′分別是查詢結(jié)果大小的準(zhǔn)確值和估計(jì)值，則稱H是支持范圍查詢時(shí)限定誤差為Const的直方圖。

文獻(xiàn)［10］中給出了采用直方極差生成限定誤差直方圖的算法（以下簡稱算法1），但是該算法生成直方數(shù)較多，因此我們提出了改進(jìn)的限定誤差直方圖，該直方圖生成算法具體描述如下：

算法2 一遍掃描二元組集合T上的元組，在生成每一個(gè)直方時(shí)，記住所遇到的最大值Max和最小值Min（當(dāng)開始一個(gè)新直方時(shí)，將vi當(dāng)作Max和Min的值）。接著計(jì)算直方hj的中位數(shù)vmid（hj）并將新的vi值與Max、Min比較，若｜vmid（hj）－Min｜＞Const，或若｜vmid（hj）－Max｜＞Const，結(jié)束本直方。與該vi值相對(duì)應(yīng)的ai不包含在該直方內(nèi)。若vi＞Max，則將vi作為新的Max值；若vi＜Min，則將vi作為新的Min值。

算法可在O（n）時(shí)間內(nèi)完成，n為對(duì)象集U 中對(duì)象的個(gè)數(shù)。

相對(duì)于算法1，改進(jìn)算法提高了數(shù)據(jù)分布不均的適用性，并且很容易可以證出，算法2生成的限定誤差為Const的直方數(shù)不多于算法1生成的限定誤差為Const的直方數(shù)。

3.2 直方圖信息存儲(chǔ)結(jié)構(gòu)

在ECHT算法中，每個(gè)節(jié)點(diǎn)需要保存對(duì)應(yīng)的直方圖信息，對(duì)于改進(jìn)的限定誤差直方圖。直方圖的第i個(gè)單元保存的信息包括：

（1）直方的上界值和下界值：UVi和LVi；

（2）對(duì)象名列表name＿list［i］壓縮數(shù)據(jù)。

定義1 （直方圖）定義T上的直方圖H 是一個(gè)三元組集合 ｛hi＝ （asi，ati，ani），1≤i≤m｝，其中 ［asi，ati］（1≤i≤m）是屬性A 的子區(qū)間，ani表示落入該區(qū)間的元組的總個(gè)數(shù)。Hi稱為直方圖的一個(gè)直方或桶，m是直方圖H 所包含的直方數(shù)。H必須滿足如下三個(gè)條件：

為了進(jìn)一步優(yōu)化直方圖的存儲(chǔ)、縮短直方圖估值的查詢時(shí)間，采用Bloom filter壓縮存儲(chǔ)對(duì)象名列表，Bloom filter是一種多哈希函數(shù)映射的快速查找算法，能夠快速判斷某個(gè)元素是否在一個(gè)集合內(nèi)。ECHT算法采用Bloom filter目的是快速判斷出對(duì)象x的取值范圍v（x）。

利用改進(jìn)的限定誤差直方圖和Bloom filter表可以快速判斷元素x的取值范圍 ［lv（x），uv（x）］，并保證估值的誤差小于Const（Const為常數(shù)）。鑒于這兩種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，確保該算法能夠滿足不同數(shù)據(jù)分布情況下Top-k查詢的要求，并降低網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量，這對(duì)Top-k查詢提供了很大的幫助。由于限定誤差直方圖是事先構(gòu)造好的，所以構(gòu)造直方圖和相應(yīng)的Bloom filter表的時(shí)間可以忽略，本文只考慮傳輸直方圖信息所帶來的帶寬消耗。為了進(jìn)一步降低帶寬消耗，中心節(jié)點(diǎn)N0預(yù)先存儲(chǔ)子節(jié)點(diǎn)的部分直方圖信息，并采用LRU策略（最近最少使用策略）維護(hù)中心節(jié)點(diǎn)存儲(chǔ)的直方圖信息，從而保證時(shí)間與空間的良好平衡

3.3 早裁剪算法

同類別的分布式Top-k查詢算法，包括TA、TPUT、TPOR、HT等算法，不能滿足不同數(shù)據(jù)分布的要求，并且數(shù)據(jù)傳輸量較大，為了避免此類算法的不足，本文提出了一種早裁剪算法。該算法旨在傳輸大量〈object，Score〉數(shù)據(jù)對(duì)前進(jìn)行數(shù)據(jù)的裁剪，算法的優(yōu)勢(shì)主要體現(xiàn)在以下三個(gè)方面：（1）通過限定誤差直方圖的信息估計(jì)對(duì)象的數(shù)值下界，提升了閾值計(jì)算的精確度，減少了大量無用數(shù)據(jù)的傳輸；（2）采用早裁剪思想，ECHT算法的第二步采用傳輸數(shù)據(jù)對(duì)象列表的方式，數(shù)據(jù)總中心結(jié)合限定誤差直方圖信息計(jì)算列表中對(duì)象的上下界，并根據(jù)數(shù)值上下界提前裁剪無用的對(duì)象；（3）子節(jié)點(diǎn)維護(hù)已上傳數(shù)據(jù)對(duì)象信息，從而避免對(duì)象值重復(fù)上傳到中心節(jié)點(diǎn)，進(jìn)一步降低了網(wǎng)絡(luò)數(shù)據(jù)傳送量。以下從兩個(gè)方面介紹早裁剪算法：

（1）確定閾值τ1和τ2。

早裁剪算法提高了閾值計(jì)算的精確度，該算法中閾值τ1和τ2的確定方法類似，算法初始階段，各節(jié)點(diǎn)將排名靠前的k個(gè)對(duì)象及其得分發(fā)送到中心節(jié)點(diǎn)，中心節(jié)點(diǎn)根據(jù)對(duì)象得分和直方圖信息估算其總分。例 如，對(duì) 象 O 的 估 計(jì) 得 分S′（O）＝f（S′1（O），S′2（O），…，S′m（O）），為了討論方便，f選用求和函數(shù)，則對(duì)象O的估計(jì)得分為：

S′（O）＝S′1（O）＋S′2（O）＋ … ＋S′m（O））（2）

若對(duì)象O在子節(jié)點(diǎn)i的得分已上傳，則S′（O）＝Si（O）；否則，在直方圖的name＿list列表查找其所在直方的下界LVi，若找到S′i（O）＝LVi，否則S′i（O）＝0。假設(shè)估計(jì)得分排名第k的估計(jì)值（即下界值）為Tl，則有：

用同樣方法可確定τ2。閾值確定引入了限定誤差直方圖信息，假設(shè)對(duì)象O的真實(shí)得分為S（O），則其估計(jì)值S′（O）與實(shí)際值S（O）滿足關(guān)系｜S（O）－S′（O）｜＜m＊Const，通常情況下估計(jì)值與真實(shí)值的誤差遠(yuǎn)遠(yuǎn)小于m＊Const，從而大大提高了閾值的計(jì)算精度。

（2）數(shù)據(jù)早裁剪規(guī)則。

ECHT算法的第二步將閾值τ1以及排名靠前的k個(gè)對(duì)象列表發(fā)送到m 個(gè)節(jié)點(diǎn)，子節(jié)點(diǎn)根據(jù)接收到的閾值τ1和k個(gè)對(duì)象列表，確定需要上傳到數(shù)據(jù)中心的對(duì)象。對(duì)象確定方法與HT算法類似，具體可參考文獻(xiàn)［9］，不同的是ECHT算法在確定需要上傳到數(shù)據(jù)中心的對(duì)象后，沒有將對(duì)象數(shù)值傳送到中心節(jié)點(diǎn)，而是將需要傳輸?shù)膶?duì)象列表采用Bloom filter壓縮并發(fā)送到中心節(jié)點(diǎn)，避免了數(shù)據(jù)對(duì)盲目上傳帶來的大量網(wǎng)絡(luò)開銷。中心節(jié)點(diǎn)計(jì)算各節(jié)點(diǎn)發(fā)送的對(duì)象的下界，并對(duì)下界值進(jìn)行排序，假設(shè)排名第k的下界值為EVk，對(duì)于排名在k以后的對(duì)象，計(jì)算其對(duì)象上界，對(duì)象O的上界值U′（O）的計(jì)算方法如下：

其中，UVi為對(duì)象O所在直方的上界值，listj是第j個(gè)節(jié)點(diǎn)已經(jīng)上傳屬性值的對(duì)象列表。

假設(shè)m個(gè)節(jié)點(diǎn)共上傳的對(duì)象集為U，數(shù)據(jù)裁剪的目的即找出這樣的對(duì)象集D，使得D中的每個(gè)對(duì)象都不可能存在于Top-k查詢的結(jié)果集。對(duì)象集D的判定方法如下：

由上述規(guī)則即可得到無需上傳的對(duì)象集D，從而避免了大量無用數(shù)據(jù)值的傳輸。

3.4 Top-k查詢結(jié)果準(zhǔn)確性分析

ECHT算法返回的結(jié)果為準(zhǔn)確的Top-k查詢結(jié)果，而非近似結(jié)果，由于Bloom filter結(jié)構(gòu)存在一定的錯(cuò)誤率，為了避免其錯(cuò)誤率帶來的影響，保證ECHT算法結(jié)束之后能夠得到準(zhǔn)確Top-k查詢結(jié)果，ECHT采用如下方法：

獲取裁剪對(duì)象集D后，中心節(jié)點(diǎn)便可以計(jì)算各節(jié)點(diǎn)需要上傳的對(duì)象集Ujnew，結(jié)合m個(gè)節(jié)點(diǎn)已上傳的對(duì)象列表listj（1≤j≤m），Ujnew采用Bloom filter表壓縮并將壓縮后的向量和閾值τ2發(fā)送到各個(gè)節(jié)點(diǎn)。Ujnew的定義如下：

ECHT選取對(duì)象集Ujnew發(fā)送對(duì)應(yīng)的網(wǎng)絡(luò)節(jié)點(diǎn)Nj，Nj選取屬性值大于閾值τ2的對(duì)象，并判斷該對(duì)象是否屬于數(shù)據(jù)對(duì)象集Ujnew，若屬于則將該對(duì)象及其屬性值發(fā)送到中心節(jié)點(diǎn)。由于Bloom filter錯(cuò)誤率僅存在于誤判屬于集合，不會(huì)把屬于這個(gè)集合的元素誤認(rèn)為不屬于這個(gè)集合，因此當(dāng)ECHT算法中Bloom filter出現(xiàn)誤判時(shí)，僅僅會(huì)產(chǎn)生極少量的冗余傳輸，而不會(huì)產(chǎn)生數(shù)據(jù)對(duì)象數(shù)據(jù)的漏傳，從而巧妙地避免了Bloom filter的錯(cuò)誤率問題，確保了返回的Top-k結(jié)果的正確性。

3.5 ECHT算法步驟

本節(jié)主要介紹ECHT算法的具體步驟，ECHT算法引入了改進(jìn)的限定誤差直方圖，使得算法能夠滿足不同數(shù)據(jù)分布的要求，另一方面提高了閾值的計(jì)算精度，結(jié)合早裁剪算法思想，進(jìn)一步提高了算法的高效性。ECHT算法的具體步驟如下：

（1）中心節(jié)點(diǎn)發(fā)送Top-k請(qǐng)求，每個(gè)節(jié)點(diǎn)將排名靠前的k個(gè)對(duì)象發(fā)送到中心節(jié)點(diǎn)，中心節(jié)點(diǎn)結(jié)合本地存儲(chǔ)的各節(jié)點(diǎn)直方圖信息計(jì)算所有對(duì)象的數(shù)值下界集合（S′）（集合（S′）的計(jì)算方法參照公式（2））。中心節(jié)點(diǎn)獲取排名靠前的k個(gè)對(duì)象，根據(jù)公式（3）計(jì)算得到閾值τ1，然后將對(duì)象列表和τ1發(fā)送到各個(gè)本地節(jié)點(diǎn)。

（2）本地節(jié)點(diǎn)收到閾值τ1和對(duì)象列表后，計(jì)算對(duì)象列表中各對(duì)象的屬性值，并取最小的屬性值Pmin。若Pmin≥τ1，將屬性值大于Pmin的對(duì)象列表及少量直方圖信息發(fā)送到中心節(jié)點(diǎn)；否則將屬性值大于τ1的對(duì)象列表發(fā)送到中心節(jié)點(diǎn)。中心節(jié)點(diǎn)收到各節(jié)點(diǎn)發(fā)送的對(duì)象列表，根據(jù)早剪切算法，獲取裁剪對(duì)象集D，并計(jì)算各節(jié)點(diǎn)需要上傳的數(shù)據(jù)對(duì)象集Ujnew（Uj的計(jì)算方法參照公式（6））。中心節(jié)點(diǎn)將對(duì)象集Ujnew采用Bloom filter算法壓縮為向量btj并與τ2并發(fā)送到本地節(jié)點(diǎn)。

（3）本地節(jié)點(diǎn)收到向量btj和τ2，將屬性值大于τ2的對(duì)象采用向量btj判斷是否屬于對(duì)象集，若屬于，則將該對(duì)象及其屬性發(fā)送到中心節(jié)點(diǎn)，否則不發(fā)送。數(shù)據(jù)中心收到各個(gè)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)后，重新計(jì)算各個(gè)對(duì)象下界，并計(jì)算下界排名第k的對(duì)象的總得分τ3，中心節(jié)點(diǎn)計(jì)算已訪問對(duì)象的上界（參考公式（4））并裁剪上界值小于τ3的對(duì)象，從而獲得候選集S。

（4）中心節(jié)點(diǎn)將候選集S發(fā)送到各個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)將尚未發(fā)送的對(duì)象的得分值發(fā)送到中心節(jié)點(diǎn)。中心節(jié)點(diǎn)重新計(jì)算S中對(duì)象的局部聚集值，然后輸出局部聚集值最高的前k個(gè)對(duì)象，即為Top-k查詢的結(jié)果。

4 實(shí)驗(yàn)與分析

本節(jié)通過實(shí)驗(yàn)評(píng)價(jià)ECHT算法的性能，并與同類TPUT算法、HT算法、KLEE算法進(jìn)行比較。實(shí)驗(yàn)沒有比較TA算法，是因?yàn)門PUT、HT等算法在絕大部分情況下的表現(xiàn)好于TA算法。KLEE是高效率的算法，但其效率是建立在損失部分正確率的基礎(chǔ)上的，在實(shí)驗(yàn)中，我們只考慮其效率，忽略該算法的錯(cuò)誤率。

實(shí)驗(yàn)中，我們選擇9臺(tái)普通PC機(jī)作為實(shí)驗(yàn)環(huán)境，分別編號(hào)為PC0～PC8。PC機(jī)的配置：CPU為 Pentium（R）Dual-Core E5800，主 頻 為 3.20 GHz，內(nèi)存為2GB，硬盤為320GB，操作系統(tǒng)為Windows XP，模擬程序由Java編寫。這里我們使用PC0作為中心節(jié)點(diǎn)，PC1～PC8作為普通節(jié)點(diǎn)。

實(shí)驗(yàn)選用的數(shù)據(jù)集是實(shí)際應(yīng)用的數(shù)據(jù)集，數(shù)據(jù)集的內(nèi)容是某海事局2012年全年一百余艘船舶機(jī)艙監(jiān)控?cái)?shù)據(jù)，數(shù)據(jù)量為TB級(jí)。限定誤差直方圖的誤差常數(shù)由數(shù)據(jù)集極差計(jì)算獲得，此處Const＝10，Bloom filter的PFP ＜0.004，依次對(duì)數(shù)據(jù)集進(jìn)行 Top-5、Top-50、Top-100查詢，得出的網(wǎng)絡(luò)帶寬消耗和查詢響應(yīng)時(shí)間結(jié)果如圖1和圖2所示。

Figure 1 Network bandwidth consumption comparison圖1 網(wǎng)絡(luò)帶寬消耗算法比較圖

Figure 2 Network response time comparison圖2 網(wǎng)絡(luò)響應(yīng)時(shí)間算法比較圖

從圖1和圖2可以發(fā)現(xiàn)，ECHT算法的網(wǎng)絡(luò)帶寬消耗和網(wǎng)絡(luò)響應(yīng)時(shí)間均優(yōu)于其他三個(gè)算法，隨著k的增加，ECHT算法的優(yōu)勢(shì)更加明顯。通過對(duì)三次查詢結(jié)果的對(duì)比發(fā)現(xiàn)，ECHT、HT和TPUT算法的Top-k查詢結(jié)果集相同，ECHT算法的 Top-k 查 詢 結(jié) 果 為 準(zhǔn) 確 Top-k 結(jié) 果 集。KLEE算法的結(jié)果集為近似Top-k結(jié)果集，三次查詢的準(zhǔn)確度分別為70%、94%和85%。

為了比較各算法對(duì)海量數(shù)據(jù)的處理性能，給出了不同數(shù)據(jù)量情況下各算法的Top-k查詢效率對(duì)比，實(shí)驗(yàn)數(shù)據(jù)分別取監(jiān)控?cái)?shù)據(jù)集的25%、50%、75%、100%，k＝100，實(shí)驗(yàn)的對(duì)比結(jié)果如圖3和圖4所示。

從圖3和圖4可以看出各算法的性能隨數(shù)據(jù)量變化的情況，隨著數(shù)據(jù)量的增大，ECHT算法的網(wǎng)絡(luò)帶寬消耗和網(wǎng)絡(luò)響應(yīng)時(shí)間的優(yōu)勢(shì)愈加明顯。本文數(shù)據(jù)量從2.5×1010到10×1010條，能夠說明算法對(duì)于海量數(shù)據(jù)處理的性能。由圖3和圖4可見，TPUT算法和HT算法需要大量的隨機(jī)查詢，特別是在海量數(shù)據(jù)情況下，產(chǎn)生了大量的數(shù)據(jù)傳輸和IO延時(shí)，算法效率較低，KLEE算法較TPUT和HT算法有優(yōu)勢(shì)；而由于ECHT算法的早裁剪和避免重傳等機(jī)制，算法表現(xiàn)優(yōu)于KLEE算法，而且隨著數(shù)據(jù)量的增大，ECHT算法的優(yōu)勢(shì)愈加明顯。

5 結(jié)束語

本文提出了一種解決海量數(shù)據(jù)分布式Top－k查詢的新算法，評(píng)價(jià)該算法的性能標(biāo)準(zhǔn)是低網(wǎng)絡(luò)帶寬消耗和低網(wǎng)絡(luò)延遲，本文研究的算法已經(jīng)初步用于某海事局船舶數(shù)據(jù)采集及管理系統(tǒng)中。實(shí)驗(yàn)及初步應(yīng)用表明，該算法相比同類算法優(yōu)勢(shì)明顯，具有較好的應(yīng)用價(jià)值。

［1］ Pang H H，Ding X，Zheng B.Efficient processing of exact top-kqueries over disk-resident sortedlists［J］.VLDB Journal，2010，19（3）：437-456.

［2］ Arai B，Das G，Gunopulos D，et al.Anytime measures for top-kalgorithms on exact and fuzzy data sets［J］.VLDB Journal，2009，18（2）：407-427.

［3］ Lu W，Chen J，Du X，et al.Efficient top-kapproximate searches against a relation with multiple attributes［J］.World Wide Web，2011，14（5-6）：573-597.

［4］ Neumann T，Bender M，Michel S，et al.Distributed top-k aggregation queries at large［J］.Distributed and Parallel Databases，2009，26（1）：3-27.

［5］ Wang Bin，Yang Xiao-chun，Wang Guo-ren，et al.Top-kquery calculations in dynamic distributed networks［J］.Journal of Computer Research and Development，2007，44（S）：85-94.（in Chinese）

［6］ Vlachou A，Doulkeridis C，N?rv?g K.Distributed top-k query processing by exploiting skyline summaries［J］.Distributed and Parallel Databases，2012，30（3-4）：239-271.

［7］ Chen B，Liang W，Yu J X.Energy-efficient skyline query optimization in wireless sensor networks［J］.Wireless Netw-orks，2012，18（8）：985-1004.

［8］ Cheng J，Liu W，Zhang S，et al.Energy-efficient top-kqurey approach in wireless sensor networks［J］.2010，37（11）：19-102.（in Chinese）

［9］ Yu H，Li H，Wu P，et al.Efficient processing of distributed top-kqueries［C］∥Proc of the 16th International Conference on Database and Expert Systems Applications，2005：65-74.

［10］ Ma Yong，Wang Yang.A new histogram method for size estimation of query result［J］.Computer Engineering ＆ Application，2004（5）：188-190.（in Chinese）

附中文參考文獻(xiàn)：

［5］ 王斌，楊曉春，王國仁，等.動(dòng)態(tài)的分布式環(huán)境下的Top-k查詢計(jì)算［J］.計(jì)算機(jī)研究與發(fā)展，2007，44（S）：85-94.

［8］ 程捷，劉文予，張勝凱，等.一種高效節(jié)能的無線傳感器網(wǎng)絡(luò) Top-k查詢算法［J］.計(jì)算機(jī)科學(xué)，2010，37（11）：99-102.

［10］ 馬勇，王焱.一種新的用于估算查詢結(jié)果大小的直方圖方法［J］.計(jì)算機(jī)工程與應(yīng)用，2004（5）：188-190.