用于重復(fù)充電運(yùn)營記錄的基于塊采樣的高效聚集查詢算法

潘鳴宇，張 祿，龍國標(biāo)，李香龍，馬冬雪，徐 亮

(1.國網(wǎng)北京市電力公司，北京100075; 2.南瑞集團(tuán)，北京102299)

(*通信作者電子郵箱bjdky123@163.com)

0 引言

近年來，大數(shù)據(jù)已廣為人知，各行各業(yè)每天積累大量的數(shù)據(jù)并進(jìn)行分析，以支持重要的商業(yè)決策。大數(shù)據(jù)的數(shù)據(jù)量以難以想象的速度增長，給數(shù)據(jù)處理帶來了極大的挑戰(zhàn)，一些應(yīng)用對查詢響應(yīng)時(shí)間提出了很高的要求。例如，日志分析通過不停地分析系統(tǒng)日志可以找到系統(tǒng)性能瓶頸或潛在的風(fēng)險(xiǎn)，如果分析時(shí)間較長而未能及時(shí)規(guī)避風(fēng)險(xiǎn)，可能造成不可估量的損失。

另外，數(shù)據(jù)分析專家或用戶通常希望可以整合多個(gè)數(shù)據(jù)源的數(shù)據(jù)進(jìn)行聯(lián)合分析決策。例如，一個(gè)好的銷售經(jīng)理會(huì)經(jīng)常上網(wǎng)搜集對比不同商家的定價(jià)，從而確定適合自己的定價(jià)。然而，從多數(shù)據(jù)源整合數(shù)據(jù)經(jīng)常引發(fā)數(shù)據(jù)質(zhì)量問題，如同一個(gè)實(shí)體可能存在多種不同的表示，即實(shí)體識別問題，也稱去重復(fù)問題。

實(shí)體識別旨在識別出所有表示相同實(shí)體的重復(fù)元組。文獻(xiàn)［1－2］概述了近年來實(shí)體識別問題的研究現(xiàn)狀及成果，文獻(xiàn)［3］研究如何提升實(shí)體識別的效率，文獻(xiàn)［4－6］研究了復(fù)雜數(shù)據(jù)上的實(shí)體識別技術(shù)，文獻(xiàn)［7－8］致力于提升實(shí)體識別準(zhǔn)確性。這些方法將實(shí)體識別作為線下預(yù)處理過程用來清洗整個(gè)數(shù)據(jù)集，找出全部的同一實(shí)體。然而，隨著數(shù)據(jù)規(guī)模的不斷增大，這種高計(jì)算復(fù)雜性的線下清洗模式已經(jīng)很難滿足實(shí)時(shí)性分析應(yīng)用的需求。文獻(xiàn)［9－17］研究了多種漸進(jìn)式實(shí)體識別方法，旨在通過部分清洗過的數(shù)據(jù)給出較好的查詢結(jié)果，然而，這些工作都針對于選擇投影連接查詢，還沒有聚集查詢相關(guān)的研究工作。眾所周知，聚集查詢是數(shù)據(jù)分析的基礎(chǔ)，快速準(zhǔn)確的聚集查詢處理為深入的大數(shù)據(jù)分析挖掘提供保障。

基于采樣的近似查詢處理是處理大數(shù)據(jù)聚集查詢的有利工具，這方面的研究可以追述到20世紀(jì)90年代末，為了保證交互式查詢的響應(yīng)時(shí)間，文獻(xiàn)［18－27］提出了多種近似查詢方法。最近，隨著大數(shù)據(jù)研究的興起，Agarwal等［21］提出了以BlinkDB為代表的新型近似查詢處理系統(tǒng)，用于處理TB級數(shù)據(jù)分析。然而在重復(fù)數(shù)據(jù)上的近似查詢處理的相關(guān)工作仍處于起步階段。

本文研究有重復(fù)數(shù)據(jù)的情況下的高效聚集查詢處理問題，將聚集查詢處理與實(shí)體識別有效地結(jié)合，快速返回滿足用戶需求的聚集結(jié)果。本文采用基于塊的采樣策略，在采集到的樣本上進(jìn)行實(shí)體識別，并根據(jù)實(shí)體識別的結(jié)果重構(gòu)得到聚集結(jié)果的無偏估計(jì)。

具體地，在Spark/MapReduce等云計(jì)算平臺(tái)中，數(shù)據(jù)以塊的形式存儲(chǔ)在分布式文件系統(tǒng)中，塊是數(shù)據(jù)在節(jié)點(diǎn)和磁盤間傳輸?shù)幕締挝?，傳統(tǒng)的元組級的簡單采樣不再高效。例如，在元組級采樣過程中，想要從分布式文件系統(tǒng)中隨機(jī)采集b個(gè)元組構(gòu)成樣本，若這b個(gè)元組在不同的塊內(nèi)，則會(huì)引發(fā)b塊數(shù)據(jù)的傳輸，網(wǎng)絡(luò)傳輸代價(jià)增大從而降低采樣的效率。另外，在有重復(fù)元組出現(xiàn)的情況下，經(jīng)典的概率學(xué)定理不能直接應(yīng)用，為此，本文提出了適用于塊采樣的聚集結(jié)果估計(jì)量，并證明該估計(jì)量可以保證給出無偏的結(jié)果估計(jì)。

總的來說，本文主要工作如下:

1)研究了有重復(fù)數(shù)據(jù)的情況下如何高效處理聚集查詢問題，該問題相關(guān)的研究工作仍處于起步階段。

2)提出了基于塊的采樣策略，高效地適用于分布式云計(jì)算環(huán)境。

3)提出了一種基于塊采樣的聚集查詢結(jié)果無偏估計(jì)量，并證明該估計(jì)量是無偏的。

1 實(shí)體識別

實(shí)體識別是數(shù)據(jù)質(zhì)量中的一個(gè)重要問題［17］，在聯(lián)合分析和數(shù)據(jù)聚合中應(yīng)用很多。實(shí)體識別旨在識別出表示同一實(shí)體的不同元組，典型的實(shí)體識別方法包含兩個(gè)階段:劃分階段和去重階段。

1.1 劃分階段

劃分是實(shí)體識別中提高效率的重要技術(shù)，它通過將元組集合劃分為小塊，使得不同塊內(nèi)的元組不可能指向相同的實(shí)體。劃分的目的是將原本需要應(yīng)用在全部元組上的實(shí)體識別算法降低到只需要應(yīng)用在一個(gè)塊內(nèi)的元組。劃分階段通過劃分函數(shù)作用在一個(gè)或多個(gè)屬性值上，得到劃分鍵，相同劃分鍵的元組會(huì)分到相同的塊內(nèi)。

劃分函數(shù)需要滿足以下兩點(diǎn):首先，如果兩個(gè)元組可能共同指向同一個(gè)實(shí)體，那么劃分函數(shù)應(yīng)該保證這兩個(gè)元組劃分后至少同時(shí)出現(xiàn)在一個(gè)塊內(nèi)。其次，如果兩個(gè)元組劃分后不在任何一個(gè)塊內(nèi)同時(shí)出現(xiàn)，則它們很大概率上不會(huì)共同指向相同實(shí)體。例如，將論文按照會(huì)議名稱劃分，那么只有發(fā)表在相同會(huì)議的論文會(huì)被劃分到一起，進(jìn)入下一步的去重階段。

1.2 去重階段

去重階段的目的是檢測、聚集然后合并重復(fù)元組，包含三個(gè)子過程:計(jì)算相似性、聚集候選對、合并候選對。

計(jì)算相似性 通過計(jì)算同一塊內(nèi)的元組的相似性，每對元組是否可能指向同一實(shí)體。這一階段通常計(jì)算代價(jià)很高，對于一個(gè)大小為n的塊，可能需要比較O(n2)個(gè)元組對的相似性?？偟膩碚f，不同的實(shí)體識別算法在計(jì)算相似性時(shí)采取的技術(shù)各種各樣，大致可以分為兩類:一種是基于相似性函數(shù)的方法;另一種是基于學(xué)習(xí)的方法?；谙嗨菩院瘮?shù)的方法需要設(shè)計(jì)一個(gè)相似性函數(shù)和一個(gè)閾值。基于學(xué)習(xí)的方法將實(shí)體識別問題建模為一個(gè)分類問題，通過訓(xùn)練分類器標(biāo)記每個(gè)元組對是重復(fù)的或者不重復(fù)的。

聚集候選對 根據(jù)上一階段計(jì)算的相似性或標(biāo)簽，將滿足條件的相似元組對劃分到無重疊的簇中，使得同一個(gè)簇內(nèi)的元組指向同一實(shí)體。

合并候選對 將每個(gè)簇中指向相同實(shí)體的元組合并為一個(gè)有代表性的實(shí)體，返回給用戶。合并函數(shù)是領(lǐng)域相關(guān)的，要根據(jù)元組具體形式確定，例如，對于數(shù)值型元組，合并函數(shù)可以為平均值，用均值代表簇內(nèi)元組的一般取值。

2 總體框架

2.1 基于塊的采樣策略

本文研究數(shù)值型聚集查詢，如 SUM、AVG、COUNT、VAR、GEOMEAN等，對于關(guān)系表R，本文研究如下查詢:SELECT op(exp(ti))FROM R

WHERE predicate GROUP BY col

其中:op表示聚集操作(SUM，AVG，COUNT);exp表示R的屬性算術(shù)表達(dá)式;predicate是屬性上的選擇條件;col是R中一個(gè)或多個(gè)列。當(dāng)op是COUNT時(shí)，exp相當(dāng)于SQL中的“*”通配符，ti表示表 R中的第 i條元組。構(gòu)造隨機(jī)變量 Xi=|R|*expp(ti)，對于給定的分組k，若ti滿足predicate條件并屬于分組k，則expp(ti)=exp(ti);否則expp(ti)=0。如果操作op是COUNT，則expp(ti)=1或0。

本文假設(shè)數(shù)據(jù)沒有重復(fù)，由于數(shù)據(jù)在分布式文件系統(tǒng)以塊的形式存儲(chǔ)，通常一塊大小為128 MB，設(shè)R有N個(gè)塊，每個(gè)塊大小為 B，則 |R|=NB，R={B1，B2，…，BN}。和簡單隨機(jī)采樣不同，基于塊的抽樣以塊為基本抽樣單元，隨機(jī)抽取n塊組成樣本 S，不失一般性，假設(shè) S={B1，B2，…，Bn}。為樣本中的每個(gè)塊構(gòu)造一個(gè)隨機(jī)變量n。

以COUNT為例，聚集結(jié)果的估計(jì)為:

令隨機(jī)變量 Yi=N·expp(Bi)，則 COUNT(R) =，即COUNT(R)是Yi的均值，又由于樣本S是從R中隨機(jī)抽取，則隨機(jī)變量Yi的觀察值獨(dú)立同分布。由中心極限定理可知，COUNT(R)服從以真實(shí)值為期望的正態(tài)分布，聚集結(jié)果的置信區(qū)間為:

其他聚集函數(shù)的估計(jì)量可以通過類似的方式構(gòu)造，且可以證明是總體聚集結(jié)果的無偏估計(jì)。上述估計(jì)量適用于總體R中沒有重復(fù)元組的情況，當(dāng)有重復(fù)元組出現(xiàn)的時(shí)候，就不能保證樣本中每個(gè)采樣單元被抽取的概率是相等的，因?yàn)橹貜?fù)出現(xiàn)的元組被采樣的概率大于其他元組，違背了中心極限定理中隨機(jī)變量獨(dú)立同分布的前提，因此在有實(shí)體重復(fù)情況下，不能直接應(yīng)用上述估計(jì)量，需要根據(jù)元組重復(fù)次數(shù)修改估計(jì)量，元組重復(fù)出現(xiàn)的次數(shù)將其定義為重復(fù)因子，然后利用重復(fù)因子修正估計(jì)量得到總體聚集結(jié)果的無偏估計(jì)。

為了確定樣本中每個(gè)元組的重復(fù)因子，需要對樣本進(jìn)行實(shí)體識別，總體框架如圖1所示。系統(tǒng)輸入是關(guān)系R={B1，B2，…，BN}，以及聚集查詢語句Q，輸出是聚集查詢結(jié)果的估計(jì)值及置信區(qū)間。首先對總體N塊數(shù)據(jù)進(jìn)行隨機(jī)采樣得到n塊數(shù)據(jù)，構(gòu)成樣本S;然后，對S進(jìn)行實(shí)體識別，檢測所有重復(fù)元組，若S中的一條元組t經(jīng)過實(shí)體識別過程，發(fā)現(xiàn)和m個(gè)其他元組重復(fù)，則t的重復(fù)因子為m。根據(jù)樣本中每個(gè)元組的重復(fù)因子，可以計(jì)算出聚集結(jié)果的無偏估計(jì)，詳情見第3章。樣本S上可以采用任何現(xiàn)有的實(shí)體識別方法，用戶可根據(jù)數(shù)據(jù)特點(diǎn)及需求選擇，本文采用經(jīng)典的基于相似性的實(shí)體識別。

圖1 聚集查詢處理總體框架Fig.1 Overall framework of aggregation query processing

2.2 樣本實(shí)體識別

通常實(shí)體識別是針對字符型數(shù)據(jù)的排字錯(cuò)誤，因此本文根據(jù)字符串的類別提供相應(yīng)的相似性函數(shù)。具體地，對于短字符串使用編輯距離作為相似性度量標(biāo)準(zhǔn)，對于長字符串使用杰卡德(Jaccard)相似性函數(shù)。

短字符串比較 如果用戶指定要去重的屬性是短字符串，只有幾個(gè)單詞，那么就使用編輯距離計(jì)算候選對之間的相似性。兩個(gè)元組之間的相似性為用戶指定的去重屬性上兩個(gè)屬性值的編輯距離，也就是將其中一個(gè)屬性值轉(zhuǎn)換為另一個(gè)屬性值所需要的最少編輯操作。一共有三種編輯操作:插入、刪除和修改。舉個(gè)例子，Apple和Aplee之間的編輯距離為2，因?yàn)樾枰獙plee的字符e刪掉，然后再插入p到A和p之間。

長字符串比較 如果用戶指定的去重屬性是由長字符串構(gòu)成的，那么使用Jaccard相似性函數(shù)計(jì)算屬性值之間的相似性。兩個(gè)字符串集合S1、S2的Jaccard相似性值定義為:

即兩個(gè)集合交集大小比兩個(gè)集合并集大小。例如，S1={A，B，C}，S2={A，C}，則J(S1，S2)=2/3。Jaccard 相似性函數(shù)同樣適用于元組之間相似性計(jì)算，將整條元組看作是各個(gè)屬性值組成的集合即可。

3 基于塊采樣的無偏估計(jì)

對樣本實(shí)體識別后，將得到樣本中每個(gè)元組的重復(fù)因子，接下來，研究如何利用重復(fù)因子重新構(gòu)造總體聚集值的估計(jì)量，使得其適用于重復(fù)數(shù)據(jù)并保證結(jié)果的無偏性。

不難發(fā)現(xiàn)，有重復(fù)數(shù)據(jù)的總體大小大于實(shí)際大小，因此在其上進(jìn)行均勻采樣，每個(gè)樣本被采到的概率發(fā)生改變，重復(fù)元組被采到的概率增大，沒有重復(fù)的元組被采到的概率減小。若一條元組ti的重復(fù)因子為m，即它表示的實(shí)體重復(fù)出現(xiàn)m次(若只出現(xiàn)一次沒有其他重復(fù)，則m=1)。ti被采到的概率為其他非重復(fù)元組的m倍，若ti出現(xiàn)在樣本S中，需要將其聚集屬性取值除以m，這樣等同于將其采樣的概率降低為1/m，從而和其他非重復(fù)元組的采樣概率相同，滿足均勻采樣的要求。

為了證明這種在樣本上降低重復(fù)元組權(quán)重的方法可以得到總體結(jié)果的無偏估計(jì)，首先證明在總體上降低重復(fù)元組權(quán)重后計(jì)算得到的聚集值和總體去重后的聚集結(jié)果一致。以SUM操作為例，其他聚集操作可以用類似的方法證明。

引理1 總體R={t11，t12，…，tNB}是由N個(gè)數(shù)據(jù)塊，共NB個(gè)元組構(gòu)成，令Ru表示R去重復(fù)后的數(shù)據(jù)集合，有NB個(gè)無重復(fù)元組，N'≤N。對于R中的任意元組tij，其重復(fù)因子為mij(mij≥1)，對R中每個(gè)元組按照重復(fù)因子降低權(quán)重后得到新集合，則 SUM(R')=SUM(Ru)。

接下來，證明可以通過樣本得到總體聚集值的無偏估計(jì)。和引理1類似，構(gòu)造S'，可以證明其上求得的SUM值乘以N/n，期望上等于總體去重后Ru上的SUM值，詳見定理1。

定理1 令S R是R上基于塊采樣得到的樣本，且|S|=nB，和引理1類似，Su為去重后的干凈樣本。對于任意Sij∈S，令mij表示Sij在總體中重復(fù)個(gè)數(shù)，對S中每個(gè)元組按照重復(fù)因子降低權(quán)重后得到集合

證明 由于采用均勻隨機(jī)采樣，因此sij和mij可視為獨(dú)立同分布的隨機(jī)變量，并且=MEAN(R')，根據(jù)期望線性可知，有=MEAN(R')代入上式可得如下關(guān)系:E(SUM(S'))=(nB·MEAN(R'))=NB·MEAN(R')=SUM(R')。由引理 1可知，SUM(R') =SUM(R)，因此，E(SUM(S'))=SUM(R)。uu

由定理1可知，可以對樣本進(jìn)行去重后計(jì)算聚集值，通過一定的變換可以得到總體的無偏估計(jì)，這樣可以大大減少清洗全部數(shù)據(jù)所需代價(jià)，既滿足了用戶精度要求，又可以快速返回計(jì)算結(jié)果。接下來，通過一個(gè)例子說明總體框架流程。

例1 假設(shè)塊大小為2，表R有6個(gè)元組，分布在3個(gè)塊內(nèi)，R={(t11，t12)，(t21，t22)，(t31，t32)}，查詢Q要計(jì)算 R上所有元組的SUM值。隨機(jī)選取一塊入樣本S，假設(shè)S={(t11，t12)}，通過實(shí)體識別得出(t11，t12)指向同一實(shí)體，(t12，t32) 指向同一實(shí)體，因此，m11=m12=2，總體SUM值的估計(jì)值為

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

本文在真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，測試本文提出的算法的準(zhǔn)確性和效率。實(shí)驗(yàn)在10個(gè)節(jié)點(diǎn)的集群上進(jìn)行，包含1個(gè)主節(jié)點(diǎn)和9個(gè)從節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有2個(gè) Intel Xeon處理器，六核，16 GB的隨機(jī)存取存儲(chǔ)器(Random Access Memory，RAM)，1 TB 的硬盤。

4.1 實(shí)驗(yàn)設(shè)置和數(shù)據(jù)集

通過以下兩個(gè)指標(biāo)衡量本文提出的方法的性能:1)樣本大小，單位為塊，表示采樣和去重的塊個(gè)數(shù)。2)錯(cuò)誤率，q%的錯(cuò)誤率表示估計(jì)值以95%概率位于真實(shí)值±q%范圍內(nèi)。

本文和當(dāng)前最好算法文獻(xiàn)［28］中提出的SampleClean(Sample and Clean framework)進(jìn)行比較，SampleClean采用的是基于元組的采樣策略，和基于塊采樣不同，另外，SampleClean是在Hive上實(shí)現(xiàn)的，通過調(diào)用Hive操作數(shù)據(jù)庫實(shí)現(xiàn)采樣，本文直接在數(shù)據(jù)集上進(jìn)行采樣，避免了中間層的開銷。為了方便對比，將本文提出的基于塊的采樣算法記為BlockSample(Block-based Sample)。

實(shí)驗(yàn)中采用的數(shù)據(jù)集包括合成數(shù)據(jù)集TPC-H(Transaction Processing performance Council-H)和真實(shí)數(shù)據(jù)集微軟學(xué)術(shù)檢索數(shù)據(jù)集(Microsoft Academic Search，MAS)。

TPC-H數(shù)據(jù)集:生成1 GB的TPC-H標(biāo)準(zhǔn)數(shù)據(jù)集(lineitem表中有6001199個(gè)元組)，lineitem的關(guān)系模式模擬工業(yè)購買記錄。隨機(jī)注入d%的重復(fù)數(shù)據(jù):80%一次重復(fù)，15%二次重復(fù)，5%三次重復(fù)。

微軟學(xué)術(shù)檢索數(shù)據(jù)集:該公開數(shù)據(jù)集包含學(xué)術(shù)論文發(fā)表信息，該數(shù)據(jù)集合中主要的錯(cuò)誤來源于重復(fù)數(shù)據(jù)，選取Jeffrey Ullman10位研究人員發(fā)表的論文進(jìn)行研究(記為publish)。原始數(shù)據(jù)集顯示Jeffrey Ullman這10位研究人員共發(fā)表了4605733篇文章，通過手動(dòng)去重，得到真實(shí)值為2554892篇。

對以上兩個(gè)關(guān)系表設(shè)計(jì)兩組聚集查詢，對lineitem表進(jìn)行SUM查詢，對publish表進(jìn)行COUNT查詢，如下所示:

SELECT SUM(quantity) FROM lineitem WHERE returnflag='A'AND linestatus='F'

SELECT COUNT(paper)FROM publish

4.2 準(zhǔn)確性

在TPC-H數(shù)據(jù)集上分別注入0.1%的重復(fù)數(shù)據(jù)和10%的重復(fù)數(shù)據(jù)，并和SampleClean進(jìn)行比較。在0.1%重復(fù)數(shù)據(jù)上，BlockSample和 SampleClean中 NormalizedSC(Normalized Sample Clean)算法比較，該算法適用于重復(fù)數(shù)據(jù)較少的情況;在10%重復(fù)數(shù)據(jù)上和SampleClean中的RawSC(Raw Sample Clean)算法比較，該算法適用于重復(fù)元組較多的情況。實(shí)驗(yàn)結(jié)果如圖2所示。

從TPC-H數(shù)據(jù)集上測試的結(jié)果可以看出，無論在較少重復(fù)數(shù)據(jù)或較多重復(fù)數(shù)據(jù)的情況下，BlockSample都可以和SampleClean達(dá)到幾乎相同的準(zhǔn)確率，另外，錯(cuò)誤率以1/SampleSize的速度下降。

為了更直觀地顯示計(jì)算結(jié)果，用圖3中的置信區(qū)間顯示結(jié)果的變化。圖3(a)是在0.1%重復(fù)數(shù)據(jù)的TPC-H上的實(shí)驗(yàn)結(jié)果，圖3(b)是真實(shí)數(shù)據(jù)集publish上的實(shí)驗(yàn)結(jié)果，可以看出，隨著樣本大小的增大，結(jié)果的置信區(qū)間逐漸縮小，估計(jì)結(jié)果最終趨近真實(shí)值(ground-truth)。

BlockSample可以達(dá)到和SampleClean幾乎相同的準(zhǔn)確率是因?yàn)樵O(shè)置SampleClean采用本文中的實(shí)體識別技術(shù)，兩者又存在一些差異，是因?yàn)槊看尾蓸佣际请S機(jī)的，得到的樣本不可能完全相同。

4.3 運(yùn)行時(shí)間

接下來，對BlockSample和SampleClean的運(yùn)行時(shí)間進(jìn)行測試，如圖4(a)所示，在重復(fù)率0.1%，大小為1 GB的TPC-H數(shù)據(jù)集上，相同樣本大小時(shí)(即準(zhǔn)確度相同)，BlockSample計(jì)算時(shí)間總是小于SampleClean，并且時(shí)間差隨著樣本增大逐漸增大，也就是說，BlockSample在數(shù)據(jù)較大的情況下性能表現(xiàn)更好。

圖2 SampleClean和BlockSample準(zhǔn)確率比較Fig.2 Accuracy comparison of SampleClean and BlockSample

圖3 不同數(shù)據(jù)集上查詢結(jié)果與置信區(qū)間比較Fig.3 Query result and confidence interval comparison on different datasets

為了證實(shí)上述猜想，在更大的數(shù)據(jù)集上進(jìn)行測試，選取TPC-H數(shù)據(jù)集，生成10 GB～100 GB的數(shù)據(jù)，重復(fù)率為0.1%，設(shè)置BlockSample和SampleClean都采取樣本大小為全部數(shù)據(jù)的10%，記錄兩個(gè)算法的運(yùn)行時(shí)間如圖4(b)所示。

由圖4(b)可以看出:在數(shù)據(jù)量較大時(shí)，BlockSample運(yùn)行時(shí)間也少于SampleClean的運(yùn)行時(shí)間;并且，當(dāng)數(shù)據(jù)線性增大時(shí)，BlockSample運(yùn)行時(shí)間呈線性緩慢增長，而SampleClean呈指數(shù)趨勢增長。通過這個(gè)實(shí)驗(yàn)，可以看出BlockSample具有更好的可擴(kuò)展性，適用于數(shù)據(jù)量較大的情況。

通過分析，共有兩點(diǎn)原因:首先，BlockSample采用基于塊的采樣策略，在Spark中，數(shù)據(jù)以塊作為基本單位進(jìn)行存儲(chǔ)和傳輸，基于元組的采樣取一個(gè)樣本就可能造成一個(gè)塊的傳輸，從而增大了I/O時(shí)間和通信時(shí)間。另外，SampleClean構(gòu)建在Hive數(shù)據(jù)庫上層，所有數(shù)據(jù)的操作都通過Hive層進(jìn)行，無疑增大了中間層的計(jì)算代價(jià)，而BlockSample是在數(shù)據(jù)上直接進(jìn)行計(jì)算，省去了中間數(shù)據(jù)管理的開銷。

圖4 不同數(shù)據(jù)集上運(yùn)行時(shí)間比較Fig.4 Running time comparison on different datasets

5 結(jié)語

本文研究了將實(shí)體識別與聚集查詢高效融合問題，提出了基于塊的采樣策略，大大提高了聚集查詢效率。另外，本文提出了適用于塊采樣和重復(fù)數(shù)據(jù)的查詢結(jié)果的估計(jì)量，并證明該估計(jì)量是無偏的。實(shí)驗(yàn)結(jié)果表明本文提出的算法能達(dá)到和當(dāng)前最好的算法相同的精確度，并且大大提高了查詢效率，能夠更好地適用于大數(shù)據(jù)情況。未來我們將研究重復(fù)數(shù)據(jù)上的嵌套聚集查詢處理方法，當(dāng)查詢嵌套時(shí)，本文提出的無偏估計(jì)量不再有效，因此，需要進(jìn)一步研究如何保證查詢結(jié)果的無偏性。