随着数据获取技术和网络应用的不断发展，数据的形式从静态逐渐扩展到了动态流形式[1]，人们常须面对高速流入的大量实时数据．这类流数据的体量过于庞大，且更新速度极快[2]，要及时地在每次数据丢失前完成Top-k查询任务，对于存储容量和处理时间均有很高要求，往往超出了现有算法的解决能力．本研究提出了一个针对流数据的Top-k查询算法，目标在于筛选出其中最大的k个元素．传统的Top-k精确查询算法须将数据全部排序，然后在排序后的集合中查找[3-4]，通用的快速排序算法时间复杂度为O(nlog n)．随着流数据的出现，Top-k精确查询的处理有了新的求解途径．最初Bruno等人通过限制性接口访问源数据来完成一次性的Top-k精确查询[5]．但是一次性的查询显然不能满足实时流数据应用的需求，于是考虑对每一次新到达的数据进行实时监控查询，将新到达的元素插入到Top-k序列中更新序列．其他常见的方法还有通过滑动窗口来监控实时流入的新数据[6]、分布式处理Top-k查询问题[7-9] 等．近年来，近似算法在流数据Top-k查询问题中有广泛的应用．文献[10]提出利用counter-base和sketch-base工具来近似估计流数据中频率最高的元素．文献[11]对比了Space-Saving，Count Skecth和Probabilistic-InPlace算法在流数据上近似估计最高频元素的准确率和时间、空间消耗．文献[12]提出一种1-pass算法，使用非常有限的存储空间来估计数据流中最频繁的项目．对于很多现实应用情况，近似Top-k即使不能达到100%的精确，也已经能够很好地满足任务的需求．但是在某些场合，特别是海量数据的情况下，这些近似算法的时间开销仍然无法满足某些实际问题的需要．在这样的背景下，概率近似正确(probably approximately correct，PAC)算法得到越来越多的关注[13]，逐渐成为解决大数据处理和分析(特别是流数据)的重要手段．传统算法里有概率算法，即计算的结果是正确的，但是得到结果有一定的概率(称为算法可信度)．也有近似算法，即计算结果满足事先规定的精度(称为算法误差)．PAC计算融合了两种算法，不仅计算结果是近似的，而且连这种近似性都是概率的，因此叫做概率近似正确算法．PAC算法在精度和可信度两个方面做了妥协，计算成本(时间、空间、通信)大大降低．由于PAC算法在近似算法的基础上，增加了可信度，进一步放宽了问题求解的要求，因此在同样的问题中，比起传统的概率算法和近似算法(甚至包括遗传算法等)有着更低的成本开销．它不一定能给出最优解，但能够在时间复杂度和空间复杂度较小的情况下，得到一个符合实际需要的可能近似解，并根据问题要求任意逼近精确解．本研究针对流数据的Top-k数值实时查询问题，应用PAC算法原理，提出了一种新的实时查询算法，通过抽样的方法来近似地估计流数据中最大的k个数据，并保证在给定的误差范围内具有较高的可信度．1 问题描述PAC算法的一般定义表述为：给定问题T，算法A称为T的PAC算法，对于任意的0β，γ1，有Pr[E(A(u),F(u))≤β]≥γ, 式中：Pr(∙)为概率函数；A(u)和F(u)分别为算法A的计算结果和问题的实际结果，其中u可以是元素，也可以是集合；E为根据不同问题定义的不同误差；β为给定的误差值；γ为可信度，表示在一次计算中，得到所要求的近似结果的概率，即所得近似结果的误差E不大于给定误差β的概率．设当前流数据集合为X，对于一个关于X的Top-k查询算法，假设查询结果近似Top-k序列为(d1,d2,⋯,dk)(didi+1)．对于该问题，定义误差的计算公式为E=|{x≥dk|x∈X}|/|X|，即X中数据不小于近似Top-k序列中dk的比例，其中|X|表示X的元素个数．流数据Top-k查询的PAC算法要求Pr(E≤β)≥γ．对于流数据Top-k查询，可以得到如下结果．命题1 存在PAC算法A，使得流数据Top-k查询的给定误差、可信度及随机抽取样本数之间满足N+1≥log(1-γk)/log(1-β)．(1)即当随机抽样样本数超过N时，可在可信度不小于γ、误差不大于β的意义下(简称PAC意义下)给出当前数据集的Top-k排序．根据命题1，在给定误差的情况下，抽样数越大，可信度越高，本研究通过实验验证了这一理论结果．当给定误差为0.01时，Top-1查询(即最大元查询)最多只须抽取多于458个样本就可以达到0.99的可信度，并且可信度不会因为数据量的增加而出现下降，这说明了所提出的PAC算法在处理近似估计流数据Top-k的问题上具有很好的稳定性．注意一个问题，根据命题1，抽样的样本数与当前数据量|X|=M无关，这是因为对于误差的定义是一个比例，即不小于dk的元素的占比不多于β，所以不会随着|X|的不同而不同．若须要计算大于dk的数据个数，则应该是βM．例如，在当前数据总量为M的情况下，要求不小于dk的元素数不超过m，则令β=m/M，需要的样本数量为N+1≥log(1-γk)/log1-m/M，这就与当前数据总量有关了．2 流数据查询的PAC算法2.1　算法描述对于流数据集合X,X={xi,i=1,2,⋯,k}，其中xi为时刻i流入的数据．设置k个随机独立的排序器Si(i=1,2,⋯,k),Si从流数据中独立随机抽取样本，并通过二分比较算法保存最大的k个数据，每个排序器Si实时返回其中的最大值di，若某两个排序器返回的数据相同，则其中一个排序器(例如序号大的)扔掉该数据，并将其第二个数据递补，直至获得k个不重复的数据．将这k个值从大到小排序，得到降序序列D=(d1,d2,⋯,dk），即为输出的Top-k序列．这个序列就是PAC意义下当前流数据中最大的k个不同的数据．之所以每个排序器保留前k个数据，是为了当数据重复时，有足够可替换的数据．在估算过程中，k个排序器分别独立从流数据中抽样，并且独立确定最大值，这相当于不放回抽样，严格地说，对于最大值的估计是有影响的．但是由于实际问题中，当前数据总量远远大于样本数N，可以忽略这个影响．2.2　理论分析先就k=1的情况进行证明．命题2 对于单个排序器，用N个随机样本中的最大数据d代替当前数据集X中的最大数据，使得误差不超过β，且可信度不小于γ，则β,γ,N三者之间满足公式N+1≥log(1-γ)/log(1-β)．(2)证明 从X中随机抽取N个数据，其中最大者为d．设X中小于d的元素占比u满足1-βu≤1，即d是最大数据的概率为u．在抽样结果已经发生的前提下(事件A)，有Pr(0≤u≤1-β|A)=Pr(A|0≤u≤1-β)∙Pr(0≤u≤1-β)/Pr(A)=(1-β)N+1.这里利用了贝叶斯公式、全概率公式，并且假定u是均匀分布．令(1-β)N+1≤1-γ，即N+1≥log(1-γ)/log(1-β)，则Pr(u1-β|A)=1-Pr(0≤u≤1-β|A)≥γ，从而证明了命题2．有了命题2作为基础，现在证明命题1．当Top-k查询算法中，k个排序器Si分别返回各自抽样的不同最大值di(i=1,2,⋯,k)，对于每个di，都以可信度γi保证其误差不超过β，因此对于X中的任意数据x，大于其中任何一个di(1≤i≤k)的概率都不超过β，且可信度大于等于∏ikγi．只要单个排序器误差为β，可信度为γk，就可以实现总体误差不超过β，可信度不小于γ，再根据式(2)确定须抽样的个数N，这就得到了命题1．须要注意的是，在上面的算法描述中，有一个舍弃递补的过程．对于一个数据集X，φ是一个随机抽取序列，φ的随机性与X中具体的数据值无关，因此从排序器Si中舍弃与另一排序器输出相同的数据di，相当于Si在另一个数据集X'中抽样，其中X'与X只是区别于di，在X'中di被一个充分小的数据替代(因此不会被选为前k个数据)，这样做既不会影响抽样的随机性，又能保证Si递补的数据符合要求．事实上，设Si返回的di被舍弃，继而递补另一个数据di*，根据抽样过程，这时di*是X'中的最大样本，并且X'中大于di*的数据不超过β|X'|个(可信度γ)，在此前提下，由于X与X'只相差一个di，因此X中大于di*的数据个数不超过β|X|+1，其与X的比例(即误差)为β+(1/|X|)．以此类推，k个排序器最坏情况误差不大于β+(k/|X|)，由于|X|一般都很大，而k一般比较小，且固定不变，因此与β相比，k/|X|≪β，可以忽略，即舍弃递补过程引起的误差微小变化可以忽略．若这类误差不能忽略，则可以根据待处理的流数据的规模M和排序器的个数k，事先估计k/M的可能最大值ε，将估算误差β*设计为β*≤β-ε．2.3　时间复杂度和样本复杂度上述算法对于流数据查询可以实时进行，随着数据的流动给出了当前流数据的前k个数据．每个独立排序器Si持续地从流数据中随机抽取样本，运行时间主要消耗在判断每一次抽取的样本是否位于前k个位置上，由于原来的顺序是已经排好的，因此采取二分查找插入，扔掉最后一个数据即可，串行时间的总开销为O(klog k)，并行时间为O(log k)．PAC算法注重抽样的个数与误差及可信度之间的关系．一般来说，要求的给定误差越小，可信度越大，需要的样本数量也越多，因此样本数量N与给定误差β、可信度γ构成函数关系，即N≥f(β,γ)，称为样本复杂度(有些文献中使用1/β和1/(1-γ)替代β和γ，使得f(1/β,1⁄(1-γ))是增函数)．在式(1)中，N依赖于给定误差β和可信度γ的对数，因此该算法有较低的样本复杂度．抽样数只依赖于给定误差和可信度，与当前数据总量无关，这也是PAC算法的一个特点，可以以较小的代价在海量的数据集里进行处理和分析．下面计算得到的几个具体抽样数：当β=0.05，γ=0.95，k=1时，N≥58；当β=0.05，γ=0.95，k=10时，N≥102；当β=0.01，γ=0.99，k=1时，N≥458；当β=0.01，γ=0.99，k=10时，N≥686；当β=0.01，γ=0.99，k=100时，N≥915；当β=0.001，γ=0.999，k=100时，N≥11 506．3 实验结果及分析3.1　实验过程实验使用连续生成的浮点随机数，取值范围为[0，1]，给定β和γ，利用k个随机独立排序器Si(i=1,2,⋯,k），获得最大值作为该排序器的输出(重复的递补)，然后从这k个输出得到Top-k排序．实验分为4个部分：a. 对单个随机独立排序器，验证给定误差下不同抽样数N得到的可信度能否符合命题2；b. 对k个随机独立排序器估计流数据中的Top-k序列，验证给定误差下不同抽样数N得到的可信度是否符合命题1，以k=10为例；c. 对于k=1，抽样数从50到500(间隔50)各进行1 000次实验，观察在给定可信度(0.90，0.95，0.99)下误差随着抽样数增加的变化；d. 对于k=10，抽样数从50到800(间隔50)各进行1 000次实验，观察在给定可信度(0.90，0.95，0.99)下误差随着抽样数增加的变化．实验过程中，第i次实验处理的数据集合为Xi，得到的Top-k序列为Di=(d1,d2,⋯,dk)，若Xi中有Ei个数据大于dk，则实测误差为βi=Ei/|Xi|．对于T次实验，若设βi≤β的次数为T*(i=1,2,⋯,T)，则实测可信度γ=T*/T．可信度越大，给定误差的Top-k的近似查询结果就越可靠．3.2　单个排序器抽样数与可信度的关系验证单个随机独立排序器获得的最大值能否作为当前数据集的最大值(PAC意义下)．根据式(2)可以得出：当给定误差β=0.01时，每个随机独立排序器抽取的样本个数N越大，可信度γ就应该越大，给定误差的最大值估计结果就越可靠．根据计算，当N≥458时应该达到0.99的可信度．为了验证这一结论，给定误差0.01，选择N分别为50，100，150，200，250，300，350，400，450，500，用单个随机独立排序器进行1 000次实验，计算在该给定误差下的可信度，结果如图1所示．实验结果验证了计算结论，给定误差0.01，随着抽样数逐渐增加，可信度逐渐增加．10.13245/j.hust.210208.F001图1单个排序器不同抽样数的可信度折线图当N=458时，将1 000次实验抽样结果的实际误差βi分布绘制成散点图(图2)．可以看到大部分误差都小于给定误差β=0.01，可信度能够达到0.991．10.13245/j.hust.210208.F002图2N=458时1 000次实验的误差散点图3.3　10个排序器抽样数与可信度的关系验证在k1个随机独立排序器上获得的Top-k序列能否很好地作为当前数据集最大的k个值．根据式(2)可以得出：对于k=10的情况，给定误差0.01，当N≥686时，计算得到的Top-10序列应该能达到0.99的可信度．为了验证这一结论，给定误差0.01，选择N=50,100,⋯,800，用单个随机独立排序器进行1 000次实验，计算在该给定误差下的可信度，结果如图3所示．实验结果验证了计算结论，给定误差0.01，随着抽样数逐渐增加，可信度逐渐增加．10.13245/j.hust.210208.F003图310个排序器不同抽样数的可信度折线图当N=686时，将1 000次实验的抽样结果的实际误差βi分布绘制成散点图(图4)．可以看到大部分误差都小于给定误差β=0.01，可信度能够达到0.99．10.13245/j.hust.210208.F004图4N=686时1 000次实验的误差散点图因此，能够在可信的误差范围内使用k个随机独立排序器得到的Top-k序列近似代替当前数据集的实际Top-k序列．3.4　给定可信度和抽样数与误差的关系为研究抽样数与误差之间的关系，对于k=1，抽样数从50到500(间隔50)各进行1 000次实验，观察在给定可信度(0.90，0.95，0.99)下误差随着抽样数增加的变化(图5)．对于给定的可信度，随抽样数的增加，误差呈现下降趋势，符合预期，即抽样数越多，所估计的结果越精确．10.13245/j.hust.210208.F005图5单个排序器不同抽样数的误差折线图对于k=10，抽样数从50到800(间隔50)各进行1 000次实验，同样观察在给定可信度(0.90，0.95，0.99)下误差随着抽样数增加的变化(图6)，图6呈现了与图5同样的趋势，即抽样数越多，误差越小，所估计的结果也越精确．10.13245/j.hust.210208.F006图610个排序器不同抽样数的误差折线图4 结论本研究提出了一种基于概率近似正确原理设计的流数据Top-k序列算法．在[0，1]之间的浮点随机数流数据集上进行了实验，实验结果验证了理论推导的正确性，证明了误差、可信度和抽取样本数之间的关系．实验很好地拟合了理论计算的结果，单个随机独立排序器抽样458个样本时就可以达到0.991以上的可信度(理论值是0.99)．因此，该算法可以有效地应对实时流数据集Top-k查询问题，也展示了PAC算法在大数据计算中的优势和特点．下一步拟尝试把该算法扩展应用到更多的现实数据集及与查询相关的其他问题上．