软件学报  2014, Vol. Issue (4): 813-825   PDF    
一种云环境下的大数据Top-K查询方法
慈祥, 马友忠, 孟小峰    
中国人民大学 信息学院, 北京 100872
摘要:Top-K查询在搜索引擎、电子商务等领域有着广泛的应用.Top-K查询从海量数据中返回最符合用户需求的前K个结果,主要目的是消除信息过载带来的负面影响.大数据背景下的Top-K查询,给数据管理和分析等方面带来新的挑战.结合MapReduce的特点,从数据划分、数据筛选等方面对云环境下的大数据Top-K查询问题进行深入研究.实验结果表明,该方法具有良好的性能和扩展性.
关键词Top-K查询     云计算     MapReduce    
Method for Top-K Query on Big Data in Cloud
CI Xiang, MA You-Zhong, MENG Xiao-Feng    
School of Information, Renmin University of China, Beijing 100872, China
Corresponding author:CI Xiang, E-mail: cixiang31415926@126.com
Abstract: Top-K query has been widely used in lots of modern applications such as search engine and e-commerce. Top-K query returns the most relative results for user from massive data, and its main purpose is to eliminate the negative effect of information overload. Top-K query on big data has brought new challenges to data management and analysis. In light of features of MapReduce, this paper presents an in-depth study of Top-K query on big data from the perspective of data partitioning and data filtering. Experimental results show that the proposed approaches have better performance and scalability.
Key words: top-K query     cloud     MapReduce    

随着大数据时代的到来,数据开始呈现爆炸式增长.不断积累的数据,对数据存储、分析等领域提出严峻的挑战.大数据的最终价值体现在数据的分析和利用上,而对数据处理时间的要求也越来越高.一般认为,数据价值会随时间的流逝而降低.因此,如何缩短数据处理时间、提高数据处理效率的问题,引起越来越多研究者的兴趣和关注.

数据量和信息量往往是矛盾的,海量数据并不一定意味着信息的丰富,很多时候反而会导致信息过载.对用户而言,有用的信息淹没在大数据的海啸之中.如何从大数据中快速提取出有用的信息,是目前大数据的核心问题之一.在搜索引擎、电子商务、移动App等诸多领域,Top-K查询是一种极其常见的查询类型.用户通过对不同属性的权值设定来反映其自身偏好,而系统则根据用户提交的权值计算并返回符合该用户需求的前K个结果.Top-K查询能帮助用户从大量数据中得到自己最关心的信息,因此,研究大数据背景下的Top-K查询问题具有非常实际和广泛的应用价值.本文的主要工作就是在云环境下,结合MapReduce特性,从数据划分和数据筛选两个方面改进大数据的Top-K查询效率.

1 相关工作 1.1 Top-K查询

Top-K查询(top-K query),又被称作序敏感查询(rank-aware query).该问题的研究最早出现于文献[1]中,主要为了解决多媒体的检索.由于很多应用场景对结果的排序有着内在的要求,Top-K问题在提出之后立刻引起关注,并在搜索引擎、多媒体检索、关系数据库等诸多领域得到了广泛的研究和应用.从数据的存储环境,可以将其划分为集中式关系数据库和分布式系统两大类.

早期Top-K问题的研究主要围绕集中式关系数据库展开.根据数据源的访问方式,又可进一步细化为3大类,即:支持有序和随机的数据访问、不支持随机的数据访问以及随机访问受限的数据访问.在支持有序和随机数据访问的算法中,最具代表性的是文献[2]提出的TA算法(threshold algorithm),NRA算法[2]和Stream- Combine[3]着重解决了数据源不支持随机访问(仅支持有序数据访问)情况下的Top-K查询.在随机访问受限的场景下,系统至少要保证一组数据源有序且随机访问以可控的方式进行,典型的算法有MPro算法[4]、Upper and Pick算法[5]以及Rank-Join算法[6].

除了常规的Top-K查询,近几年来,一些特殊类型的Top-K问题也被提了出来,例如Reverse Top-K[7, 8].

随着数据量的增大,分布式Top-K查询越来越受到关注.从数据划分的方式来看,分布式环境下的Top-K问题可以归纳为垂直划分和水平划分两大类.所谓的垂直划分是数据按属性进行划分,类似于关系数据库的列存储方式,早期的分布式Top-K查询研究多使用这种划分方式.文献[9]研究了网络中分散的Web数据库,其假设的前提是所有数据库支持随机和有序访问.文献[10]中提出了TPUT(three-phase uniform threshold)方法.KLEE[11]则对TPUT进行改进.水平划分是按元组来划分,类似于关系数据库的行存储方式.在该划分方法下,文献[12]通过对查询结果的缓存来提高查询的效率.文献[13]尝试减少用户的查询等待时间,但却会带来较大的数据传输开销.文献[14]提出了一种称为SPEERTO的方法进行分布式Top-K查询,其核心思想是利用Skyline作为辅助的数据概要进行数据处理.文献[15]对文献[14]中的方法作了进一步的完善,提出了称为DiTo的一整套处理框架.

1.2 MapReduce简介

MapReduce[16]是Google公司提出的一种编程模型.MapReduce会将用户的原始数据进行分块,然后交给不同的Map任务去处理.Map任务会从输入中解析出Key/Value对,用户自行定义的Map函数作用于这些Key/Value对,并得到相应的中间结果,该结果会被写入本地硬盘.Reduce任务从硬盘上读取数据后,根据key值进行排序,将具有相同key值的组织在一起.最后,用户自定义的Reduce函数会作用于这些排好序的结果并输出最终结果.图 1[16]展示了一个典型的MapReduce任务的执行过程.

Fig. 1 Execution overview of MapReduce图 1 MapReduce执行流程图

关于MapReduce的介绍很多,这里不再赘述.详细实现可参考文献[16].MapReduce模型简单,且现实中很多问题都可转化到MapReduce框架中进行处理.因此该模型公开后,立刻受到极大关注,并在文本挖掘、信息检索等领域得到广泛的应用.Google的MapReduce有多种开源实现,应用最广泛的是Hadoop的MapReduce,本文方法也是以此为基础而实现的.

围绕着Top-K查询问题,近些年来开展了很多有益的研究工作.但是关系数据库以及传统的分布式环境都很难有效应对大数据环境下的Top-K查询,主要原因在于数据对象及处理方法产生了很大的变化.

(1) 云环境和传统的分布式系统存在较大差异.

从架构上来看,传统的分布式系统,比如P2P,节点之间基本对等.而以Hadoop为代表的云计算系统,其数据控制和数据处理分开,有独立的节点分别完成数据控制和数据处理的任务,节点之间有一定的层次关系.从数据存储方式来看,云环境中的数据一般以块(block)的形式进行存储,每个块中会包含一批数据;而传统的数据存储常常以元组(tuple)为单位进行存储,块的粒度远大于元组.从这个角度来看,以元组作为存储单位设计的一些Top-K算法在云环境下并不适用,例如支持随机访问特定记录的Top-K算法.

(2) MapReduce基本成为云环境下数据批处理的标准框架.

MapReduce是一种典型的主从式架构,由master节点和slave节点构成,其中,master节点负责控制流,而slave节点则负责具体的数据处理流.slave节点之间一般不进行通信,也就是说,数据处理过程中不会进行实时的信息共享.另外,原始的MapReduce是一种批处理的方式,处理过程中不会有最终结果的任何子集产生,直到处理结束才会一次性返回所有结果.

由于存在上述巨大的差异,云环境下的大数据Top-K查询面临着新的挑战.Top-K问题在MapReduce框架下有很直接的解决方案,即,利用MapReduce进行数据排序再返回前K个值.这种方案既符合MapReduce批处理的特点,也容易实现,但其最大的缺点就是处理时间过长.每次到来一个新的查询,就要对全部数据进行一次处理,数据量巨大和查询频繁时该方法均不可取.目前,国内外结合MapReduce特性对Top-K查询进行专门优化的工作不多.RanKloud[17]考虑利用MapReduce解决多媒体数据的Top-K检索问题.通过系统运行时统计信息的收集来决定查询结束条件,但是并不能保证检索的结果一定是前K个,可能会出现检索值小于K的情况.文献[18]探讨了利用MapReduce处理Top-K查询的一些基本问题,但是文章本身并没有对其提到的各种问题进行深入探讨,也未对其方法的有效性进行实验验证.总的来说,目前并没有一种经过验证的可行方案能够较好地解决云环境下利用MapReduce对大数据进行Top-K查询的问题.

2 云环境下的Top-K查询 2.1 问题定义和基本概念

假设数据集为T,数据集的势(cardinality)为m,则T={ti:1≤im}.数据的维度Dim(T)=d,因此,每个ti可以表示成{t1(d),t2(d),…,ti(d)},且所有的属性均为数值型.对于Top-K问题而言,查询函数f通常是一个单调递增函数(increasingly monotone function).即,如果对"1≤nd,ti(n)≤tj(n),则f(ti)≤f(tj).

最常用的单调函数是加权和(weighted sum),本文亦采用加权和进行相关的计算.

假设权值向量w=(w1,w2,…,wn),则此时的.f(ti)值越大,代表排序越高.在此定义下的Top-K查询就是返回最大的前k个值.不失一般性,本文假设wiÎ[0, 1],$wj>0.这表明,权值向量中允许有分量为0,但不能全为0.表 1对上述符号进行了归纳.

Table 1 Overview of symbols 1 相关符号描述

图 2展示了在此定义下的一个Top-K查询过程和最终结果.

Fig. 2 Typical top-K query图 2 典型的Top-K查询

为了简化问题以及阐述方便,本文作如下合理的假设:

1) 数据集相对固定,或者数据的更新速度相对于整个数据集而言,可以在一定时间段内忽略不计.很多实际的应用场景符合这种假设,例如,淘宝网的商品数据虽然时刻在更新,但是相对于其整个庞大的商品基数而言,可以认为在某个固定时间内(比如1周)变化不大.对于变化频繁的数据集,比如流数据,本文的方法并不适用;

2) 数据分布均匀.在数据量足够大的情况下,很多场景的数据基本上符合这个要求;

3) 任意记录在其任意维的值均不为负值.现实中的应用基本符合该假设.例如,对某饭店或某商品评分,每项分值肯定大于等于0.即使不符合,也可以通过简单的数据转换,将其数据范围转换到非负区间;

4) 所使用的服务器数量大致和数据量保持一个合理的比例.数据过多或过少,可以分别通过增加或减少服务器来实现负载平衡.

很多领域都存在着Top-K问题,由于存在需求上的差异,没有一种通用的方法能够适用于所有的Top-K问题.基于上述假设不难发现,本文方法比较适用于多次查询和参数自由变化的Top-K查询.这类查询在现实中很多,比如电子商务领域,用户在购买一个商品之前,可能会根据商品的多个属性组合进行搜索,以便确定是否购买.

2.2 数据划分

云环境下,数据划分的基本原则是,尽可能地将数据均匀地划分到各个服务器上.这种均匀不仅体现在数据量的均匀上,更重要的是面对特定应用时,这种划分能够尽可能地保证每个服务器上的数据对最后结果均有贡献.在以MapReduce为数据处理框架的云环境下,垂直划分方式不太适合,因为每个子集只有原数据集的部分属性,这样在每次计算时需要访问所有子集才能得到一个完整的加权值,而在MapReduce中,slave节点之间一般不会进行信息交换.考虑到MapReduce的这种特点,本文采用水平划分方式.进一步地,在Top-K领域具有代表性的水平划分方式有如下几种:随机划分、基于网格、基于角度和基于超平面.假设将记录的每个属性作为一个维度,则n维Top-K问题中的每条记录等价于n维空间的一个数据点(下文中,数据点和记录表示同一概念,可以混用,不再解释).为了便于理解这几种数据划分方式,以二维数据(即,每条记录有两个属性)为代表,具体的划分方法如图 3~图 6所示.

Fig. 3 Random partitioning图 3 随机划分

Fig. 4 Grid partitioning图 4 网格划分

Fig. 5 Angle-Based partitioning图 5 基于角度的划分

Fig. 6 Hyperplane-Based partitioning图 6 基于超平面的划分

图 3是随机数据划分方式,对于新的数据点,通过某种方式,比如round-robin,将数据点随机地分配到某个服务器.图 4是网格划分,这种方法将整个数据空间划分成若干个网格,落入某个网格中的数据点则分配到相对应的服务器.图 5描述了二维情况下基于角度的数据划分,这种方法首先将笛卡尔坐标系的数据点通过转换规则映射到超球坐标系(hyperspherical coordinate),在此基础上,对每个维度的数据进行划分,最终得到结果.图 6是基于超平面的划分,该方法的本质是将空间数据映射到某个特定的超平面(在二维空间,超平面等价于一个直线),图例中选择的超平面为直线x+y=1,具体的映射规则是,将通过数据点和原点的直线与超平面的交点作为该数据点在超平面上的映射点.完成映射之后,通过对各个数据维度进行划分来完成整个数据空间的划分.该方法可以很容易地推广到更高维空间.基于角度和基于超平面的划分都首先要对数据进行转换映射,区别在于:基于角度的划分数据坐标系发生改变,而基于超平面的划分还是在相同的坐标系.从计算复杂度来看,随机划分方式最为简单,而基于角度的划分方式最为复杂.

针对Top-K问题,随机划分和基于网格的划分效率不高,原因在于:虽然数据被划分到多个服务器上,但是每个服务器上计算的Top-K值对最终Top-K值的贡献是不同的.以加权和最大为Top-K的衡量标准,则在图 3图 4所示的随机划分和网格划分中,靠近右上角分区中的数据更有可能成为最终的全局Top-K值,而左下角的分区数据极可能毫无贡献.这必然会造成计算资源的浪费和计算效率的低下.最理想的状态是:每个数据分区都能计算出部分的全局Top-K值,这样就能够充分发挥系统的并行特性且充分利用计算资源.因此,基于角度的划分和基于超平面的划分是可能的候选方法,这两种数据划分方式最早都是在分布式Skyline计算中引入的.由于具有一些内在的联系,Skyline的计算在很大程度上和Top-K有共通之处.但是考虑到MapReduce的特性,直接使用这两种方法都不太合适,主要原因在于,直接使用这两种划分方式对于后期的数据删选而言不够高效.因此,本文提出一种同时考虑角度和距离的划分方式.进行基于角度的划分,首先需要将欧式空间的数据点坐标转化至超球坐标.具体转换规则如下:

假设数据点的坐标t=[t(1),t(2),…,t(d)],则其相对应的超球坐标由一个径向坐标rd-1个角度坐标f1,f2,…, fd-1构成,其中,

(1)

考虑到第2.1节中的假设3),则0≤fip/2,对"1≤id-1.为了便于理解,接下来以二维空间为例解释本文的划分方法,但具体的方法可以扩展到任意维.图 7是在假设有3台服务器的前提下,利用本文基于角度和距离的数据划分方式对整个数据空间进行的划分.

Fig. 7 Angle and distance-based partitioning图 7 基于角度和距离的数据划分

具体步骤如下:

1. 依据公式(1)对整个数据空间的数据点进行数据转换,从笛卡尔坐标系转换至超球坐标;

2. 采用类似网格划分的方式对角度进行划分.此步骤划分仅考虑角度坐标,不考虑径向坐标.网格划分技术相对成熟,有很多可借鉴的划分方式,本文采用较易实现的等分划分方式,其中,等分的数量等于服务器的数量.例如在图 7中,根据角度坐标将整个平面首先分成了3个部分,其中,

3. 经过步骤2,每个角度区间都占据了数据空间的一个部分,由于第2.1节中的假设2),我们可以认为每个角度区间所占有的数据量大致相同.在此基础上,利用径向坐标r对每个区间的数据作进一步的划分.此步骤的划分区间数量可以根据实际需求进行改变,但需保证以下两点:

1) 在对r进行划分时粒度不能过细,至少保证二次划分的子区间包含一个块的数据量.由于第2.1节假设4)的保证,每个服务器上会有相对充足的数据量进行划分;

2) 二次划分的子区间面积相等,即,图 7中的区间1~区间9的面积应当相等.这主要是为了保证每个子区间的数据量大致相等.

以上方法是在二维空间中进行的,推广到三维空间则是对1/8的球体进行划分,更高维的话没有直观的几何图形,但划分方法一致,只是计算复杂度有所增加.在云环境下,相对原始的基于角度的划分,本文方法有一定的优势,详细分析在下文中会加以阐述.

2.3 基于MapReduce的大数据Top-K查询 2.3.1 数据筛选

在云环境下,加速Top-K计算最核心的方法有两种:

(1) 将计算过程并行化,本文通过MapReduce来实现;

(2) 减少计算所需的数据量.下面将结合第2.2节中提到的数据划分方法来阐述本文数据筛选的方法.

对于方法2,需要思考的关键性问题是:在加权和的计算方式下,对于一个特定的Top-K查询,如果从几何角度考虑,究竟空间中满足何种性质的数据点最终会成为Top-K点?

为了解释方便,同样以二维空间的数据点为例.

假设现在有若干个数据点,这些点在二维坐标系中的位置如图 8所示.如果现在的权值向量w=(0.5,0.5),那么对于所有记录而言,0.5x+0.5y的值决定了其最终的排序.如果将权值向量也看作空间中的一个点(称为权值点),那么过原点和权值点可以构成一条直线(图 8中的直线y=x).此时,Top-K查询有如下性质:

性质1. 假设权值向量w=(w1,w2,…,wn),空间中有限数据点的集合t={t1,t2,…,tn},则对集合t中任意点tx,计算,可以得到集合L={L1,L2,…,Ln}.如果L中,值小于或等于Lx的点有k个,则点tx在权值向量为w、以加权和为查询函数的Top-K查询中的最终排序为n-k.

Fig. 8 Geometric interpretation of top-K query图 8 Top-K查询的几何解释

该性质的证明和解释可参见文献[19],这里不再证明.性质1表明:在Top-K查询中,如果以加权和作为查询函数,则数据点在空间中的排序由其在通过原点和权值点构成的直线上的投影位置所决定.可以直观地理解为:数据点在直线上的投影位置距离原点越远,其排序越高;或者说投影长度越长,排序越高.空间中点t到过原点和权值点的直线的投影长,根据L值很容易判断点之间的排序关系.假设现在需要查询如图 8所示的数据空间中的Top-3点,则这些点为t1,t2,t3,且排序关系是t1>t2>t3.

本文在角度之外加入距离的划分因素,最大的好处就是能够确定每个划分区间的距离范围,该距离范围可以用于数据筛选.如图 9所示,在确定数据划分和权值向量之后,通过各维度的数值区间和角度区间信息,可以计算出分区3所对应的投影长度区间为(L1,L2),也就是说,区间3中所有点的投影长度均大于等于L1,小于等于L2.其他区间均可得到其相对应的投影长度区间.但在面对不同的权重值时,区间内可能取到最小和最大投影值的点会发生变动,导致计算复杂度增加.为了简化计算,本文提出松弛投影范围的概念.利用此概念可以大大减少数据筛选的计算量.可以观察到,按照本文的划分方法,每个子区间都可以被一个最小外接超立方体所包围.无论权值向量如何变化,该立方体具有最小和最大投影值的点始终是[tmin(1),tmin(2),…,tmin(d)]和[tmax(1), tmax(2),…,tmax(d)].图 10展示了二维空间中这种计算方式(二维空间中的超立方体退化为矩形),图中虚线部分是相对应区间的最小外接超立方体,区间1~区间3对应的最小和最大投影值点均在图中标示出来.从图中还可以发现,此时的投影长度区间实际上是真实投影长度区间的一个超集,区间范围有所扩大.但是,这种方法因为最大和最小投影点固定,在面对不同的权值时,可以非常简单地计算出对应的区间,且对于实际的筛选效果影响不是很大.

Fig. 9 Computation of projected range图 9 投影范围计算

Fig. 10 Relaxed projected range图 10 松弛投影范围

数据划分完成之后,根据区间的距离信息可以确定每个区间在其相对应服务器上的排序(根据与原点间距离,由远到近),同时也可以确定松弛投影范围概念下的最小和最大投影点.将这些元数据信息以表的形式保存在master节点上,表 2是一个实例.

Table 2 Metadata for data filtering 2 用于数据筛选的元数据

表 2中的每格代表相应区间的元数据,最前面数字表示区间号,例如第1格中的3.区间号之后的两组数据分别表示松弛投影范围概念下的最小和最大投影点坐标.处于表中同一行,代表其位于同一个距离区间,例如第1行表示最外一层的区间3、区间6、区间9,以此类推.

假设总的数据点为m个,总的划分区间是n个,因为在划分时保证每个划分区间的面积相等且有第2.1节中提及的假设2),可以认为每个区间的数据点大致相等,为m/n个.那么,通过比较m/nk值,就可以确定最终计算所需区间.算法1描述了利用表 2中元数据进行数据筛选的过程.

Algorithm 1. Data Filtering.

Input: k and w;

Output: Data Partitioning which will be used as the data source of MapReduce.

1. p=éK/(m/n)ù;        /*p is upper bounds of K/(m/n)*/

2. Scan metadata table, get line 1 to p;

3.     for i=1 to p;

4.         for j=1 to q ;                 /*q is the number of column*/

5.             Vmin[i][j]=tmin×w/|w|;             /*Minimal relaxed projection value*/

6.             Vmax[i][j]=tmax×w/|w|;             /*Maximal relaxed projection value*/

7.         end for;

8.         Compare all pairs of (Vmin[i][j],Vmax[i][j]);

9.         if Vmax[i][s]≤Vmin[i][t];

10.             Delete data partitioning s;

11.         else;

12.             Output s;

13. end for;

表 2中数据为例,具体步骤如下:

(1) 如果m/n>k,则可以保证最终的Top-k值只出现在划分中最外侧区间(图 9中的区间3、区间6、区间9),在此基础上,根据表 2,对这3个区间作进一步计算.如果3个区间的松弛投影区间均有重叠部分,则3个区间不能进一步筛除,需要全部计算,否则可以进一步筛除.假如权值w=(0.5,0.5),则可以利用表 2中的数据计算出区间3、区间6、区间9的松弛投影区间分别为.3个区间均互有重叠,因此无法进一步筛除,需要全部进行计算.又假设权值w=(0,1),则此时区间3、区间6、区间9相对应的松弛投影区间为.区间3和区间6有重叠,但区间9的最大松弛投影值为,比区间3的最小松弛投影值还要小,区间9可以被进一步筛除.因此,在权值w=(0,1)的情况下,需要计算的区间仅仅是区间3和区间6.

(2) 如果k/2≤m/nk,则除了最外侧之外,还要加入次外侧区间(图 9中的区间2、区间5、区间8);然后,对区间2、区间5、区间8采用类似步骤1中的方法进一步筛除数据.

(3) 如果k/3≤m/nk/2,则计算所需的区间还要再往内侧增加,以此类推.

实际中,m/n的值不光大于k,常常远大于k,例如搜索引擎中的海量数据.而我们最关心的往往只是结果第1页的几十个数据,因此,采用本文的数据划分和筛选方法,一般情况下仅需计算区间3、区间6、区间9所对应区间的block中的数据即可,减少了2/3甚至更高的数据量,大大提高了效率.

2.3.2 具体Top-K计算流程

图 11是在本文方法下的Top-K查询框架.

Fig. 11 Top-K query in cloud图 11 云环境下的Top-K查询

从整个过程来看,包括预处理和查询处理两个部分,具体步骤如下:

(1) 对数据进行预处理,主要是利用上文的方法进行数据划分,最终数据以block形式存入HDFS中;

(2) 用户提交新的查询,master节点接受参数kw,利用其上的元数据信息按照算法1的步骤对区间进行筛选,确定参与最终计算的区间号;

(3) MapReduce任务只对涉及到的区间进行计算,返回Top-K值.

3 实验和结果分析 3.1 实验环境

实验在一个由11个节点组成的集群上进行,其中,1个节点作为master节点,其余10个节点作为slave节点.节点配置如下:CPU:Q9650 3.00GHz,Memory:8GB,Disk:500GB,OS:64bit Ubuntu9.10 server,节点上运行的Hadoop版本为1.0.0.由于没有合适规模的真实数据集,本文按照表 3的数据格式生成了一批均匀分布的数据,其中每条记录的维度为10,所有值均为0~1000之间的整数,共10亿条记录,大约75G的数据量.

Table 3 Data format 3 数据格式
3.2 实验结果与分析

首先需要说明的是,本文的数据划分作为预处理过程出现,一次预处理可以为后续的多次查询提供服务,因此,预处理时间未计入总时间.下面的实验若无特别说明,计算数据量均为全部数据,参数均取k=5000,w=(0.1, 0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1).

3.2.1 执行时间对比

目前尚未发现与本文特别相关的方法,因此为了进行对比,本文另外实现了一种原始的Top-K算法和一种简单改进的Top-K算法.原始的Top-K算法思路非常直接,根据权重值,利用MapReduce对原始的数据进行排序,然后返回所需的k个最大值.简单改进的Top-K算法中的Mapper不输出所有的值,而仅输出本地Top-K到Reducer中,最后由Reducer返回全局Top-K.图 12展示了这3种方法的执行时间.

Fig. 12 Comparison of execution time图 12 执行时间对比

图 12中可以看出:原始方法时间最长;简单改进后的算法执行时间有较大幅度的缩短;本文方法的执行时间最短,且相对原始方法执行时间减少得很明显.

3.2.2 扩展性

从两个方面考察本文方法的扩展性:

· 首先,保持数据量不变,改变计算的服务器数量.从图 13可以发现:随着服务器数量的增加,执行时间虽然不是完全线性地减少,但是减少的趋势是很明显的;

Fig. 13 Scalability (servers)图 13 可扩展性(服务器数量)

· 然后,保持记录数量,但改变数据维度,即,对所有的数据记录分别取其前2个、4个、6个、8个及10个属性进行计算.从图 14可以看出:计算所需的时间呈上升趋势,但上升的幅度相对稳定,未出现随着维度的增加计算时间大幅增加的情况.

Fig. 14 Scalability (data dimension)图 14 可扩展性(数据维度)

以上两个方面都说明了本文方法的可扩展性较好.

3.2.3 不同k值对执行时间的影响

图 15展示了不同k值下执行时间的变化情况.从实验结果来看:当数据大小固定时,执行时间并不是随着k值的增加而增加,也就是说,本文方法对k的取值不是特别敏感.分析发现:虽然实验中k的取值已经较大,但由于整个记录规模巨大,使得每个区间的记录数也非常大,导致面对不同k值时,筛选出的候选block集合基本一致,也就是说,这些不同k值实际计算的数据基本相同,因此,最终计算时间相差不多.

Fig. 15 Effect of K on execution time图 15 K值变化对执行时间的影响
3.2.4 不同权值对执行时间的影响

取4组比较有代表性的权值类型进行比较,分别是等值权重w1=(0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1)、极度偏向某一属性的w2=(1,0,0,0,0,0,0,0,0,0)、较为偏向某一属性的w3=(0.73,0.03,0.03,0.03,0.03,0.03,0.03,0.03, 0.03,0.03)以及有偏向但是不明显的w4=(0.2,0.1,0.1,0.05,0.1,0.05,0.15,0.15,0.05,0.05).

图 16中可以看出:w1w4的执行时间大致相同,而w2w3的执行时间大致相同.主要是因为,当根据本文的方法对某属性计算极度或较高偏好时,候选的区间会被进一步地筛选,有部分区间会在这个步骤被排除,总的计算量降低,导致最终的执行时间变短.

Fig. 16 Effect of weight value on execution time图 16 权值对执行时间的影响
4 结 语

本文针对云环境下的大数据Top-K查询问题,利用空间角度和距离对整个数据进行划分,考虑到MapReduce在计算中slave节点之间不进行信息实时共享的特性,在数据划分的基础上提出了一种简便的数据筛选方法.实验结果表明:在绝大多数情况下,本文方法能够大幅减少计算量,提高计算效率.同时,本文的方法也有较好的扩展性.

未来将会对现有工作进行一系列的改进,主要包括:

· 考虑将本文方法进一步扩展到数据非均匀分布的情况;

· 考虑增加缓存层,对Top-K查询的结果进行缓存,因为实际中同样的查询很可能会重复出现;

· 同时,考虑进一步细化数据划分,使得面对较小的k值时处理时间能够进一步缩短.

参考文献
[1] Fagin R. Combining fuzzy information from multiple systems. Journal of Computer and System Sciences, 1999,58(1):83-99 .
[2] Fagin R, Lotem A, Naor M. Optimal aggregation algorithms for middleware. Journal of Computer and System Sciences, 2003,66(4): 614-656 .
[3] Güntzer U, Balke W, Kießling W. Towards efficient multi-feature queries in heterogeneous environments. In: Proc. of the Int’l Conf. on Information Technology: Coding and Computing (ITCC 2001). Piscataway: IEEE, 2001.622-628 .
[4] Chang KCC, Hwang SW. Minimal probing: Supporting expensive predicates for top-k queries. In: Proc. of the 2002 ACM SIGMOD Int’l Conf. on Management of Data. New York: ACM Press, 2002.346-357 .
[5] Bruno N, Chaudhuri S, Gravano L. Top-K selection queries over relational databases: Mapping strategies and performance evaluation. ACM Trans. on Database Systems, 2002,27(2):153-187 .
[6] Ilyas IF, Aref WG, Elmagarmid AK. Supporting top-k join queries in relational databases. In: Proc. of the 29th Int’l Conf. on Very Large Databases. San Fransisco: Morgan Kaufmann Publishers, 2003.207-221 .
[7] Vlachou A, Doulkeridis C, Kotidis Y, Nørvåg K. Reverse top-k queries. In: Proc. of the 26th IEEE Int’l Conf. on Data Engineering. Piscataway: IEEE, 2010.365-376 .
[8] Vlachou A, Doulkeridis C, Kotidis Y, Nørvåg K. Monochromatic and bichromatic reverse top-k queries. IEEE Trans. on Knowledge and Data Engineering, 2011,23(8):1215-1229 .
[9] Marian A, Bruno N, Gravano L. Evaluating top-k queries over Web-accessible databases. ACM Trans. on Database Systems, 2004, 29(2):319-362 .
[10] Cao P, Wang Z. Efficient top-K query calculation in distributed networks. In: Proc. of the 23th Annual ACM Symp. on Principles of Distributed Computing. New York: ACM Press, 2004. 206-215 .
[11] Michel S, Triantafillou P, Weikum G. KLEE: A framework for distributed top-k query algorithms. In: Proc. of the 31st Int’l Conf. on Very Large Data Bases. New York: ACM Press, 2005. 637-648. http://dl.acm.org/citation.cfm?id=1083667 .
[12] Zhao KP, Tao YF, Zhou SG. Efficient top-k processing in large-scaled distributed environments. Data and Knowledge Engineering, 2007,63(2):315-335 .
[13] Dedzoe WK, Lamarre P, Akbarinia R, Valduriez P. ASAP top-k query processing in unstructured P2P systems. In: Proc. of the 10th IEEE Int’l Conf. on Peer-to-Peer Computing. Piscataway: IEEE, 2010. 1-10 .
[14] Vlachou A, Doulkeridis C, Nørvåg K, Vazirgiannis M. On efficient top-k query processing in highly distributed environments. In: Proc. of the 2008 ACM SIGMOD Int’l Conf. on Management of Data. New York: ACM Press, 2008. 753-764 .
[15] Vlachou A, Doulkeridis C, Nørvåg K. Distributed top-k query processing by exploiting skyline summaries. Distributed and Parallel Databases, 2012,30(3-4):239-271 .
[16] Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters. Communications of the ACM, 2008,51(1):107-113 .
[17] Candan KS, Kim JW, Nagarkar P, Nagendra M, Yu RW. RanKloud: Scalable multimedia data processing in server clusters. IEEE MultiMedia, 2011,18(1):64-77 .
[18] Doulkeridis C, Nørvåg K. On saying “enough already!” in MapReduce. In: Proc. of the 1st Int’l Workshop on Cloud Intelligence. New York: ACM Press, 2012.7-7 .
[19] Tsaparas P, Palpanas T, Kotidis Y, Koudas N, Srivastava D. Ranked join indices. In: Proc. of the 19th IEEE Int’l Conf. on Data Engineering. Piscataway: IEEE, 2003. 277-288 .