魏賢全，鄭洪源，丁秋林

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

1 引言

近年來，隨著云計算和數(shù)據(jù)密集型運算領(lǐng)域迅速發(fā)展，數(shù)據(jù)處理規(guī)模不斷擴大，為分布式環(huán)境下Top-k查詢帶來了新的挑戰(zhàn)，如何在海量分布式數(shù)據(jù)中實現(xiàn)Top-k查詢成為了研究的熱點。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é)點，Top-k查詢的目的是在大量的數(shù)據(jù)中找出用戶最為關(guān)心的k個值。例如，通過谷歌搜索“Top-k”，返回結(jié)果約有 3 680 000 000條。為了使用戶有良好的使用體驗，搜索引擎系統(tǒng)需能夠快速地返回評分結(jié)果最高的前k個查詢結(jié)果。

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

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

2 問題描述

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

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

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

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

3 ECHT算法

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

3.1 改進限定誤差直方圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 早裁剪算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.5 ECHT算法步驟

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

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

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

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

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

4 實驗與分析

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

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

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

從圖1和圖2可以發(fā)現(xiàn)，ECHT算法的網(wǎng)絡(luò)帶寬消耗和網(wǎng)絡(luò)響應(yīng)時間均優(yōu)于其他三個算法，隨著k的增加，ECHT算法的優(yōu)勢更加明顯。通過對三次查詢結(jié)果的對比發(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%。

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

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

5 結(jié)束語

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

［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）

附中文參考文獻：

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

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

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