用于重复充电运营记录的基于块采样的高效聚集查询算法

潘鸣宇，张 禄，龙国标，李香龙，马冬雪，徐 亮

(1.国网北京市电力公司，北京100075; 2.南瑞集团，北京102299)

(*通信作者电子邮箱bjdky123@163.com)

0 引言

近年来，大数据已广为人知，各行各业每天积累大量的数据并进行分析，以支持重要的商业决策。大数据的数据量以难以想象的速度增长，给数据处理带来了极大的挑战，一些应用对查询响应时间提出了很高的要求。例如，日志分析通过不停地分析系统日志可以找到系统性能瓶颈或潜在的风险，如果分析时间较长而未能及时规避风险，可能造成不可估量的损失。

另外，数据分析专家或用户通常希望可以整合多个数据源的数据进行联合分析决策。例如，一个好的销售经理会经常上网搜集对比不同商家的定价，从而确定适合自己的定价。然而，从多数据源整合数据经常引发数据质量问题，如同一个实体可能存在多种不同的表示，即实体识别问题，也称去重复问题。

实体识别旨在识别出所有表示相同实体的重复元组。文献［1－2］概述了近年来实体识别问题的研究现状及成果，文献［3］研究如何提升实体识别的效率，文献［4－6］研究了复杂数据上的实体识别技术，文献［7－8］致力于提升实体识别准确性。这些方法将实体识别作为线下预处理过程用来清洗整个数据集，找出全部的同一实体。然而，随着数据规模的不断增大，这种高计算复杂性的线下清洗模式已经很难满足实时性分析应用的需求。文献［9－17］研究了多种渐进式实体识别方法，旨在通过部分清洗过的数据给出较好的查询结果，然而，这些工作都针对于选择投影连接查询，还没有聚集查询相关的研究工作。众所周知，聚集查询是数据分析的基础，快速准确的聚集查询处理为深入的大数据分析挖掘提供保障。

基于采样的近似查询处理是处理大数据聚集查询的有利工具，这方面的研究可以追述到20世纪90年代末，为了保证交互式查询的响应时间，文献［18－27］提出了多种近似查询方法。最近，随着大数据研究的兴起，Agarwal等［21］提出了以BlinkDB为代表的新型近似查询处理系统，用于处理TB级数据分析。然而在重复数据上的近似查询处理的相关工作仍处于起步阶段。

本文研究有重复数据的情况下的高效聚集查询处理问题，将聚集查询处理与实体识别有效地结合，快速返回满足用户需求的聚集结果。本文采用基于块的采样策略，在采集到的样本上进行实体识别，并根据实体识别的结果重构得到聚集结果的无偏估计。

具体地，在Spark/MapReduce等云计算平台中，数据以块的形式存储在分布式文件系统中，块是数据在节点和磁盘间传输的基本单位，传统的元组级的简单采样不再高效。例如，在元组级采样过程中，想要从分布式文件系统中随机采集b个元组构成样本，若这b个元组在不同的块内，则会引发b块数据的传输，网络传输代价增大从而降低采样的效率。另外，在有重复元组出现的情况下，经典的概率学定理不能直接应用，为此，本文提出了适用于块采样的聚集结果估计量，并证明该估计量可以保证给出无偏的结果估计。

总的来说，本文主要工作如下:

1)研究了有重复数据的情况下如何高效处理聚集查询问题，该问题相关的研究工作仍处于起步阶段。

2)提出了基于块的采样策略，高效地适用于分布式云计算环境。

3)提出了一种基于块采样的聚集查询结果无偏估计量，并证明该估计量是无偏的。

1 实体识别

实体识别是数据质量中的一个重要问题［17］，在联合分析和数据聚合中应用很多。实体识别旨在识别出表示同一实体的不同元组，典型的实体识别方法包含两个阶段:划分阶段和去重阶段。

1.1 划分阶段

划分是实体识别中提高效率的重要技术，它通过将元组集合划分为小块，使得不同块内的元组不可能指向相同的实体。划分的目的是将原本需要应用在全部元组上的实体识别算法降低到只需要应用在一个块内的元组。划分阶段通过划分函数作用在一个或多个属性值上，得到划分键，相同划分键的元组会分到相同的块内。

划分函数需要满足以下两点:首先，如果两个元组可能共同指向同一个实体，那么划分函数应该保证这两个元组划分后至少同时出现在一个块内。其次，如果两个元组划分后不在任何一个块内同时出现，则它们很大概率上不会共同指向相同实体。例如，将论文按照会议名称划分，那么只有发表在相同会议的论文会被划分到一起，进入下一步的去重阶段。

1.2 去重阶段

去重阶段的目的是检测、聚集然后合并重复元组，包含三个子过程:计算相似性、聚集候选对、合并候选对。

计算相似性 通过计算同一块内的元组的相似性，每对元组是否可能指向同一实体。这一阶段通常计算代价很高，对于一个大小为n的块，可能需要比较O(n2)个元组对的相似性。总的来说，不同的实体识别算法在计算相似性时采取的技术各种各样，大致可以分为两类:一种是基于相似性函数的方法;另一种是基于学习的方法。基于相似性函数的方法需要设计一个相似性函数和一个阈值。基于学习的方法将实体识别问题建模为一个分类问题，通过训练分类器标记每个元组对是重复的或者不重复的。

聚集候选对 根据上一阶段计算的相似性或标签，将满足条件的相似元组对划分到无重叠的簇中，使得同一个簇内的元组指向同一实体。

合并候选对 将每个簇中指向相同实体的元组合并为一个有代表性的实体，返回给用户。合并函数是领域相关的，要根据元组具体形式确定，例如，对于数值型元组，合并函数可以为平均值，用均值代表簇内元组的一般取值。

2 总体框架

2.1 基于块的采样策略

本文研究数值型聚集查询，如 SUM、AVG、COUNT、VAR、GEOMEAN等，对于关系表R，本文研究如下查询:SELECT op(exp(ti))FROM R

WHERE predicate GROUP BY col

其中:op表示聚集操作(SUM，AVG，COUNT);exp表示R的属性算术表达式;predicate是属性上的选择条件;col是R中一个或多个列。当op是COUNT时，exp相当于SQL中的“*”通配符，ti表示表 R中的第 i条元组。构造随机变量 Xi=|R|*expp(ti)，对于给定的分组k，若ti满足predicate条件并属于分组k，则expp(ti)=exp(ti);否则expp(ti)=0。如果操作op是COUNT，则expp(ti)=1或0。

本文假设数据没有重复，由于数据在分布式文件系统以块的形式存储，通常一块大小为128 MB，设R有N个块，每个块大小为 B，则 |R|=NB，R={B1，B2，…，BN}。和简单随机采样不同，基于块的抽样以块为基本抽样单元，随机抽取n块组成样本 S，不失一般性，假设 S={B1，B2，…，Bn}。为样本中的每个块构造一个随机变量n。

以COUNT为例，聚集结果的估计为:

令随机变量 Yi=N·expp(Bi)，则 COUNT(R) =，即COUNT(R)是Yi的均值，又由于样本S是从R中随机抽取，则随机变量Yi的观察值独立同分布。由中心极限定理可知，COUNT(R)服从以真实值为期望的正态分布，聚集结果的置信区间为:

其他聚集函数的估计量可以通过类似的方式构造，且可以证明是总体聚集结果的无偏估计。上述估计量适用于总体R中没有重复元组的情况，当有重复元组出现的时候，就不能保证样本中每个采样单元被抽取的概率是相等的，因为重复出现的元组被采样的概率大于其他元组，违背了中心极限定理中随机变量独立同分布的前提，因此在有实体重复情况下，不能直接应用上述估计量，需要根据元组重复次数修改估计量，元组重复出现的次数将其定义为重复因子，然后利用重复因子修正估计量得到总体聚集结果的无偏估计。

为了确定样本中每个元组的重复因子，需要对样本进行实体识别，总体框架如图1所示。系统输入是关系R={B1，B2，…，BN}，以及聚集查询语句Q，输出是聚集查询结果的估计值及置信区间。首先对总体N块数据进行随机采样得到n块数据，构成样本S;然后，对S进行实体识别，检测所有重复元组，若S中的一条元组t经过实体识别过程，发现和m个其他元组重复，则t的重复因子为m。根据样本中每个元组的重复因子，可以计算出聚集结果的无偏估计，详情见第3章。样本S上可以采用任何现有的实体识别方法，用户可根据数据特点及需求选择，本文采用经典的基于相似性的实体识别。

图1 聚集查询处理总体框架Fig.1 Overall framework of aggregation query processing

2.2 样本实体识别

通常实体识别是针对字符型数据的排字错误，因此本文根据字符串的类别提供相应的相似性函数。具体地，对于短字符串使用编辑距离作为相似性度量标准，对于长字符串使用杰卡德(Jaccard)相似性函数。

短字符串比较 如果用户指定要去重的属性是短字符串，只有几个单词，那么就使用编辑距离计算候选对之间的相似性。两个元组之间的相似性为用户指定的去重属性上两个属性值的编辑距离，也就是将其中一个属性值转换为另一个属性值所需要的最少编辑操作。一共有三种编辑操作:插入、删除和修改。举个例子，Apple和Aplee之间的编辑距离为2，因为需要将Aplee的字符e删掉，然后再插入p到A和p之间。

长字符串比较 如果用户指定的去重属性是由长字符串构成的，那么使用Jaccard相似性函数计算属性值之间的相似性。两个字符串集合S1、S2的Jaccard相似性值定义为:

即两个集合交集大小比两个集合并集大小。例如，S1={A，B，C}，S2={A，C}，则J(S1，S2)=2/3。Jaccard 相似性函数同样适用于元组之间相似性计算，将整条元组看作是各个属性值组成的集合即可。

3 基于块采样的无偏估计

对样本实体识别后，将得到样本中每个元组的重复因子，接下来，研究如何利用重复因子重新构造总体聚集值的估计量，使得其适用于重复数据并保证结果的无偏性。

不难发现，有重复数据的总体大小大于实际大小，因此在其上进行均匀采样，每个样本被采到的概率发生改变，重复元组被采到的概率增大，没有重复的元组被采到的概率减小。若一条元组ti的重复因子为m，即它表示的实体重复出现m次(若只出现一次没有其他重复，则m=1)。ti被采到的概率为其他非重复元组的m倍，若ti出现在样本S中，需要将其聚集属性取值除以m，这样等同于将其采样的概率降低为1/m，从而和其他非重复元组的采样概率相同，满足均匀采样的要求。

为了证明这种在样本上降低重复元组权重的方法可以得到总体结果的无偏估计，首先证明在总体上降低重复元组权重后计算得到的聚集值和总体去重后的聚集结果一致。以SUM操作为例，其他聚集操作可以用类似的方法证明。

引理1 总体R={t11，t12，…，tNB}是由N个数据块，共NB个元组构成，令Ru表示R去重复后的数据集合，有NB个无重复元组，N'≤N。对于R中的任意元组tij，其重复因子为mij(mij≥1)，对R中每个元组按照重复因子降低权重后得到新集合，则 SUM(R')=SUM(Ru)。

接下来，证明可以通过样本得到总体聚集值的无偏估计。和引理1类似，构造S'，可以证明其上求得的SUM值乘以N/n，期望上等于总体去重后Ru上的SUM值，详见定理1。

定理1 令S R是R上基于块采样得到的样本，且|S|=nB，和引理1类似，Su为去重后的干净样本。对于任意Sij∈S，令mij表示Sij在总体中重复个数，对S中每个元组按照重复因子降低权重后得到集合

证明 由于采用均匀随机采样，因此sij和mij可视为独立同分布的随机变量，并且=MEAN(R')，根据期望线性可知，有=MEAN(R')代入上式可得如下关系:E(SUM(S'))=(nB·MEAN(R'))=NB·MEAN(R')=SUM(R')。由引理 1可知，SUM(R') =SUM(R)，因此，E(SUM(S'))=SUM(R)。uu

由定理1可知，可以对样本进行去重后计算聚集值，通过一定的变换可以得到总体的无偏估计，这样可以大大减少清洗全部数据所需代价，既满足了用户精度要求，又可以快速返回计算结果。接下来，通过一个例子说明总体框架流程。

例1 假设块大小为2，表R有6个元组，分布在3个块内，R={(t11，t12)，(t21，t22)，(t31，t32)}，查询Q要计算 R上所有元组的SUM值。随机选取一块入样本S，假设S={(t11，t12)}，通过实体识别得出(t11，t12)指向同一实体，(t12，t32) 指向同一实体，因此，m11=m12=2，总体SUM值的估计值为

4 实验与结果分析

本文在真实数据集和合成数据集上进行实验，测试本文提出的算法的准确性和效率。实验在10个节点的集群上进行，包含1个主节点和9个从节点，每个节点有2个 Intel Xeon处理器，六核，16 GB的随机存取存储器(Random Access Memory，RAM)，1 TB 的硬盘。

4.1 实验设置和数据集

通过以下两个指标衡量本文提出的方法的性能:1)样本大小，单位为块，表示采样和去重的块个数。2)错误率，q%的错误率表示估计值以95%概率位于真实值±q%范围内。

本文和当前最好算法文献［28］中提出的SampleClean(Sample and Clean framework)进行比较，SampleClean采用的是基于元组的采样策略，和基于块采样不同，另外，SampleClean是在Hive上实现的，通过调用Hive操作数据库实现采样，本文直接在数据集上进行采样，避免了中间层的开销。为了方便对比，将本文提出的基于块的采样算法记为BlockSample(Block-based Sample)。

实验中采用的数据集包括合成数据集TPC-H(Transaction Processing performance Council-H)和真实数据集微软学术检索数据集(Microsoft Academic Search，MAS)。

TPC-H数据集:生成1 GB的TPC-H标准数据集(lineitem表中有6001199个元组)，lineitem的关系模式模拟工业购买记录。随机注入d%的重复数据:80%一次重复，15%二次重复，5%三次重复。

微软学术检索数据集:该公开数据集包含学术论文发表信息，该数据集合中主要的错误来源于重复数据，选取Jeffrey Ullman10位研究人员发表的论文进行研究(记为publish)。原始数据集显示Jeffrey Ullman这10位研究人员共发表了4605733篇文章，通过手动去重，得到真实值为2554892篇。

对以上两个关系表设计两组聚集查询，对lineitem表进行SUM查询，对publish表进行COUNT查询，如下所示:

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

SELECT COUNT(paper)FROM publish

4.2 准确性

在TPC-H数据集上分别注入0.1%的重复数据和10%的重复数据，并和SampleClean进行比较。在0.1%重复数据上，BlockSample和 SampleClean中 NormalizedSC(Normalized Sample Clean)算法比较，该算法适用于重复数据较少的情况;在10%重复数据上和SampleClean中的RawSC(Raw Sample Clean)算法比较，该算法适用于重复元组较多的情况。实验结果如图2所示。

从TPC-H数据集上测试的结果可以看出，无论在较少重复数据或较多重复数据的情况下，BlockSample都可以和SampleClean达到几乎相同的准确率，另外，错误率以1/SampleSize的速度下降。

为了更直观地显示计算结果，用图3中的置信区间显示结果的变化。图3(a)是在0.1%重复数据的TPC-H上的实验结果，图3(b)是真实数据集publish上的实验结果，可以看出，随着样本大小的增大，结果的置信区间逐渐缩小，估计结果最终趋近真实值(ground-truth)。

BlockSample可以达到和SampleClean几乎相同的准确率是因为设置SampleClean采用本文中的实体识别技术，两者又存在一些差异，是因为每次采样都是随机的，得到的样本不可能完全相同。

4.3 运行时间

接下来，对BlockSample和SampleClean的运行时间进行测试，如图4(a)所示，在重复率0.1%，大小为1 GB的TPC-H数据集上，相同样本大小时(即准确度相同)，BlockSample计算时间总是小于SampleClean，并且时间差随着样本增大逐渐增大，也就是说，BlockSample在数据较大的情况下性能表现更好。

图2 SampleClean和BlockSample准确率比较Fig.2 Accuracy comparison of SampleClean and BlockSample

图3 不同数据集上查询结果与置信区间比较Fig.3 Query result and confidence interval comparison on different datasets

为了证实上述猜想，在更大的数据集上进行测试，选取TPC-H数据集，生成10 GB～100 GB的数据，重复率为0.1%，设置BlockSample和SampleClean都采取样本大小为全部数据的10%，记录两个算法的运行时间如图4(b)所示。

由图4(b)可以看出:在数据量较大时，BlockSample运行时间也少于SampleClean的运行时间;并且，当数据线性增大时，BlockSample运行时间呈线性缓慢增长，而SampleClean呈指数趋势增长。通过这个实验，可以看出BlockSample具有更好的可扩展性，适用于数据量较大的情况。

通过分析，共有两点原因:首先，BlockSample采用基于块的采样策略，在Spark中，数据以块作为基本单位进行存储和传输，基于元组的采样取一个样本就可能造成一个块的传输，从而增大了I/O时间和通信时间。另外，SampleClean构建在Hive数据库上层，所有数据的操作都通过Hive层进行，无疑增大了中间层的计算代价，而BlockSample是在数据上直接进行计算，省去了中间数据管理的开销。

图4 不同数据集上运行时间比较Fig.4 Running time comparison on different datasets

5 结语

本文研究了将实体识别与聚集查询高效融合问题，提出了基于块的采样策略，大大提高了聚集查询效率。另外，本文提出了适用于块采样和重复数据的查询结果的估计量，并证明该估计量是无偏的。实验结果表明本文提出的算法能达到和当前最好的算法相同的精确度，并且大大提高了查询效率，能够更好地适用于大数据情况。未来我们将研究重复数据上的嵌套聚集查询处理方法，当查询嵌套时，本文提出的无偏估计量不再有效，因此，需要进一步研究如何保证查询结果的无偏性。