论文研究-不确定数据流上高效可扩展的并行Skyline查询算法 .pdf

所需积分/C币:10 2019-08-19 12:00:13 702KB .PDF
6
收藏 收藏
举报

不确定数据流上高效可扩展的并行Skyline查询算法,赵越,王意洁,随着信息技术的不断发展,针对不确定数据流的应用和研究逐步引起学界的广泛关注。目前不确定数据流上Skyline查询的相关研究多关注��
山国武获论文在丝 http:/www.paper.edu.cn 国防科技大学的王广东等人对不确定数据流上的并行 Skyline算法进行了研究,建立 了不确定薮据流 Skyline査询的并行处理框架,并提岀了并行算法 PSUDS,明确了不确定数 据流上并行 Skyline査询的方法,并通过实验表明 PSUDS算法具有良好的负载均衡能力。 但是该算法采用的并行模型可扩展性受到限制 上述算法采用的都是在已知的概率阈值条件下通过剪枝策略减少支配关系测试次数的 方法。此类优化方法虽然具有较高的剪枝效率,但只适用于p- Skyline査询,适用性不强。 不确定数据流上并行 Skyline查询所面临的查询范围未知时,例如响应具有不同需求的用 户的即席查询( ad-hoc query)时,可能无法有效地应用剪枝算法减少支配关系测试次数。因此, 硏究高效可扩展的不斫定数据流上的并行 Skyline查询算法是非常有现实意义的 902不确定数据流上 Skyline查询的并行模型 本节首先给出不确定薮据流上并行 Skyline查询的相关定义;然后介绍现有的不确定数 据流并行 Skyline查洵处理模型,并分析其优缺点。 21术语与问题定义 为了分析不确定数据流的并行 Skyline査询的处理流程,首先明确不确定数据流 Skyline 95查询的相关定义。首先给出多维确定性数据集下 Skyline的定义。对于一个数据空间D,D 具有d个维度{d1…;d,S为D上的一个具有n个元素的数据集合,对于S中的任意点l∈S, 可以表示为u={u…;u小,其中表示u在d维度的值。不失一般性地,假设在任意维度 d上的值b有u≥0,并且在每一维度上,都是u值越小越优。 定义1支配)对于D上的两点Lv∈S,若(1)在每一个维度dED上,都有≤W,并且(2) 100在全少一个维度d∈D上,有u<v,则u支配v,表小为u<v 定义2 (Skyline) Skyline是指一个D上点的集合SKY(S)∈S,若对于比∈SKYS),都个存 在有veS,且<u,则sKYS)中的点则被称作 Skyline点( Skyline point,SP) 为了易于表述,并且与此前不确定数据流 Skyline查询上的部分相关工作6,7相一致,本 文采用点概率的数据模型表示不确定数据流。令DS表示所处理的不确定数据流,DSν表示 105当前处理的不确定数据流上的长度为N的滑动窗口。DS屮的不确定元组a由两部分组成: 概率p和多维元组a,即<cpa>,p称为元组a的存在概率。定义两个不确定元组a和B 之间的支配关系为:a支配B当日仅当g支配B,a支配β仍然记作a-f 不确定数据流 Skyline査询,求取的是DSw内的元组a成为 Skyline点的概率,也称为 该元组(在DS内)的仝局 Skyline概率,记作Py(e)。针对点概率模型而言,对于Dsw内的 10任-元纽s,Pky(a)=plm=w-(1-p-)。通常为了控制返回结果的规模,不确定数据流 Skyline查询多返回的为Pk()不小于一定阈值概率4的元组的集合,即 SYMa==/EDS1(Bk(e)≥4)但为了不失般性,在本文中不确定数据流 Skyline查 询返回的是滑动窗口内的所有元组的Pk(e) 通过上述定义,不确定数据流的并行 Skyline査询就是通过对数据进行划分,在不确定 115数据流 Skyline查询过程中并行地进行支配关系测试,以达到提高查询效率的目的。在本义 中,对数据采用水平划分的方式,下面讨论的并行处理模型也以数据水平划分为基础。 22不确定数据流的并行 Skyline查询处理模型 不确定数据流的并行 Skyline査询对并行模型及相应的査询算法主要有以卜儿点需求: 1.不需要对数据的集中预处理,因为数据流查询具有实吋性、适应性等要求,而数据流的到 山国武获论文在丝 http:/www.paper.edu.cn 120达具有不确定性,所以要求算法的执行不需要对数据的进行集中预处理;2.查询结果具有渐 进性,对于每次的 Skyline査询,查询过程中得到的部分最终结果能够在得到之后尽快地返 回,而不是等所有的最终结果都岀来之后再返回:3.支持数据的多样性,多样性包括对数据 类型、维度等没有特定的要求 在文献[7中对不确定数据流的并行 Skyline查询给出了基于滑动窗口划分的并行处理 125框架,如图1所示,分发节点M负责缓存和分发数据,各并行节点P(1≤公m)负责接收消 息并根据消息对本地元组进行处理。 Input data stream 图1不确定数据流的并行 Skyline查询处坦框架 Fig. I Parallel processing framework for skyline query on uncertain data stream 130 在只体地个确定数据流的并行 Skyline查洵过程中,主要采用了基于该框架的两种并行 模型——简单并行模型( simple parallel model,SPM和全分布并行模型( distributed parallel model,DPM),如图2所示。两者的区别主要在」SPM模型中,并行节点之问没有通信,每 个并行节点都独立的存储并维护滑动窗∏的全局信息,而DPM中,并行节点只存储属于自 己的局部滑动窗口内的元组,通过并行节点见的通信获取滑动窗口的全局信息。 Data stream ns Data stream d P R P 135 (a)简单并行模型 (b)全分布并行模型 (a) Simple parallel model (b) Distributed parallel model 佟2并行处理模型 Fig 2 Parallel processing model 140 在上述的并行模型中,SPM模型由于并行节点需要额外存储整个滑动窗口内的全局信 息,导致滑动窗口的人小受到并行节点性能的限制,同时并行节点本地的存储开销和计算开 销也相对较人。SPM模型的优点在于并行节点间不需要通信,受到的通信开销方面的限制 很小,具有良好的可扩展性。而DPM模型中,并行节点只存储属于自己的局部滑动窗口的 元组信息,随着滑动窗口的増大,本地计算开销増长较小,并可以通过増加并行节点缓解原 145先各并行节点的压力。但是全分布并行模型主要有以下几点不足:1.随着并行度的增加,并 行节点间的通信链路效目呈指薮级增长,导致通信丌销的影响随并行节点薮目增加而显著增 加,可扩展性不够;2.各并行节点间需要数据的相互传输以协同节点内部的处理过程,同步 操作导致并行节点的性能不能得到充分利用。 4 山国武获论文在丝 http:/www.paper.edu.cn 3基于分步并行模型的不确定数据流上的 Skyline查询算法 150 本文的日标是构建高效可扩展的支持不确定数据流的并行 Skyline查询的算法。为了提 高算法本身的适用性,在本文中,针对的不确定数据流 Skyline査洵均为全概率查询,即不 釆用阈值进行剪枝的求取所有滑动窗口内元组成为 Skyline点的概率的查询 31分步并行模型(STPM) 为了吸收SPM模型中并行节点间不需要通信协同的优点,又能克服其需要存储全局滑 155动窗口内数据的不足,我们提出了分步并行模型( step-parallel model,STPM),图3给出的是 STPM模型的处理流程。该模型将原先的SPM模型中的并行节点所执行的任务划分成3个 模块,每个模块内采用专门的并行节点执行该模块的任务。首先将SPM模型中并行节点内 仝局滑动窗口维护的任务与分发节点M的任务合并,形成数据分发模块。然后,由个确定 数据流的并行 Skyline查询的定义中给出的求取全局 Skyline概率的公式 160P3()= pellaedsNas(1-p)可知,支配关系测试的过程中并不需要考察元组的全局 Skyline概 率,计算个元组e的全局 Skyline概率,只需要知道e的存在概率和所有支配e的元组的 存在概率即可。因此,将并行节点基于执行任务的不同划分为支配关系测试和全局 Skyline 概率计算两个模块:支配关系测试模块内的并行节点只存储本地的元组信息,并通过本地的 元组信息进行支配关系测试,求取全局 Skyline概率计算的部分中间结果;全局 Skyline概 65率计算模块接收数据分发模块的元组更新消息用于维护全局窗口,接收支配关系测试模块的 概率更新消息用于维护仝局 Skyline概率。关于STPM模犁中各模块并行节点上具体的处理 算法将在第3.2节详细讨论。 支配关系测试 数据流来源 数据分发组 更 后 skyline相 率计算 消息 图3分步并行模型(STPM)的处理流程 170 Fig3 The process of step-parallel mode 具体来说,STPM模型最大的优势是更细粒度的拆分了计算任务,使查询处埋过程流水 更深,并行度开发更好。首先,每一个模块内部各并行节点间不需要通信,能够更为专注地 执行计算任务,新增节点所需要增加的链路数目较少。其次,各模垬可以根据所执行任务的 不同计算量采用不同的并行度,更为有效地利用计算资派。最后各模块之间的任务执行流水 175化,提高查询效率 32基于分步并行模型的 Skyline查询算法 本节将讨论STPM模型各模块并行节点上的算法实现。 首先,数据分发模块接收到不确定数据流中的新到达元组ε后,检査自身维扩的全局滑 动窗口是否已满,若全局滑动窗口已满,则广生失效元组e并将新到达元组和失效元组的 山国武获论文在丝 http:/www.paper.edu.cn 180消息发送给支配关糸测试模块中的每个并行节点和全局 Skyline计算模块中元组所在的并 行节点。 算法1分发模块的处理算法 Input:新到达元组e; Output:新到达元组e;失效元组e; 1:若仝局滑动窗口未淓,则将ε加入仝局滑动窗口 2:若仝局滑动窗口已满 21:将c入全局滑动窗口; 22:从滑动窗口屮弹出失效元组 3:将ε发送给攴配关系测试模块中所有并行节点; 4:将ε发送给全局 Skyline概率计算模块中对应节点; 5:若存在失效元组e 5.1:将e′发送给支配关系测试模块中所有并行节点 52:将e′发送给全局 Skyline概率计算模块中对应节点 然后,攴配关系测试模块中的并行节点接收到消息后,对本地元组进行维护,并将维扩 过程中全局 Skyline慨率发生变化的元组的概率更新信息发送给全局 Skyline概率计算模块 下面给出支配关系测试模块中并行节点上的处理算法。 算法2文配关系测试模块中并行节点的处算法 Input:新到达元组e;失效元纽e’ Output:新到达元组引起的概率史新消息<v,(1-p)x, 失效元组′引起的概率更新消息<v(1-p/)÷> 新到达元组e的局部 Skyline概率<//e/<a(1-p),>>; 1:处理新到达元组e 1.1:若ε属于北并行节点,则将ε加入到木地元组集合中,找到支配φ的元组集合B和被∈文配的元 组A 12:否则,在本地元组集合中找到支配a的元组集合B和被e支配的元组A; 13:根据B中每个元组B计算刀∈m(1p) 14:发送概率更新消息<,v瓶-(1-p),X>到全局 Skyline概率计算模块中a所在并行节点 1.5:对A屮每个元组u,发送概率更新消息<v(1p)X>到全局 Skyline概率计算模块屮u所在 并行节点; 2:若存在失效元组e 21:若φ'属于此并行节点,在本地元组集合屮将e′删除,找到被e′支配的元组A 22:否则,在本地元组集合中找到被e′攴配的元组A; 23:对A中每个元组v,发送概率更新消息<v(1p)÷>到全局 Skyline概率计算模块中v所在并 行节点; 185 最后,全局 Skyline概率计算模块屮的并行节点接收到元组更新消息后,根据消息的内 容添加新到达元组刪除失效元组e;接收到概率更新消息后,根据消息的内容对相应的 元组执行概率更新操作。下面给出全局 Skyline概率计算模块中并行节点上的处珥算法。 算法3全局 Kylin概率计算模坎中并行节点的处理算法 Input:元组更新消息;概率更新消息;控制消息 Output:全局 Skyline结果; 1:若消息类型为元组史新消息 11:若为新到达元组a,则将e存入本地元组集合,将a的全局 Skyline概率置为e的存在概率; 12:若为失效元组a′,则将e′从本地元组集合删除 2:若消息类型为概率更新消息<LpC> 山国武获论文在丝 http:/www.paper.edu.cn 21:从本地元组集合找到元组 22:将u的全局 Skyline概率根据C规定的操作,乘以或除以概率P 3:若消息类型为控制消息,则根据消息,在概率史澌完成后发送全局 Skyline结果 4实验 41实验环境设置 本文中实验采用 Twitter storn数据流处理平台实现了SPM模型和STPM模型,并把 Stor集群部署在20台2G内存双核的 CentOS系统的虚拟机构成的集群上,通过该集群测 试基于两种并行模型的查询算法的性能。 实验中,分别对滑动窗口大小为50K,100K,200K,400K,并行度为4,8,16,32,数据维 度为2,4,8条件下的单次查询的平均响应时间( response time)和平均处理时间( process time)进 195行考察。其中平均响应时间是指两次连续查询中间的间隔时间,平均处理时间是指单次査洵 并行节点内部的处理时间。此外,需要说明的是,并行度并非指采用的虚拟机的数日,而是 指Stom集群中并行执行支配关系测试的任务数目。 4.2实验结果分析 4.2.1数据维度大小对查询性能的影响 200 实验过程中,对基于STPM模垩的査询算法与基于SPM模型的算法,在数据维度大小 为2,4,8,并行度为16,滑动窗口大小为200K条件下,进行不确定数据流的并行 Skyline 查询的性能对比,如图5所小。 SPM Response Time :.. STPM Response Time -- SPM Process Time STPM Process Time Number of dimensions 图5不同数据维度下单次查询的半均响应时间和半均处理时间 205 omparison of the response time and process time at different data dimensions 从图5可知,数据维度的增加对查询吋间的增加影响较小,主要原因是在 Skyline查询 中,对于两个元组之间的支配关系的测试并不一定需要比对元组的每一个维度,当通过元组 的前几维数据能够确定支配关系不存在时,支配关系测试就会终止。 以各维数据独立同分布的2维元组和4维元组作对比:2维元组做支配关系测试需要比 210对每一个维度的数据;4维元组做支配关系测试时,只有通过前2维数据无法确定支配关系 的元组之间会对第3维数据进行比对,而只有通过前3维数据无法确定支配关系的元组之间 才会比较第4维数据。因此,虽然元组的数据维度增加了,但增加的数据维度中的数据参与 支配关系测试的概率是逐步降低的 同时,由于数据维度的增加,相同大小的滑动窗口内元组之间存在的支配关系随之减少 215每次新元组到达和旧元组失效需要更新概率的元组数目也随之减少,以STPM模型为例, 儒要在支配关系测试模块和全局 Skyline概率计算模块之间传递的数据量减少,从而减少上 山国武获论文在丝 http:/www.paper.edu.cn 述两模块之间数据传输的吋间廾销。 422滑动窗口大小对查询性能的影响 实验过程中,对基于SIPM模型的査询算法与基于SPM模型的算法,在滑动窗凵大小 220为50K,100K,200K,400K,数据维度为2,并行度为16条件下,进行不确定数据流的并行 Skyline查询的性能对比,如图6所示 SPM Response Time--X-- PM Response Time SPM Process Time…-… STPM Process Time 10 8642 首 50100150200250300350400 Slide Window siz9(×10° 图6不同滑动窗口下单次查狗的平均响应时间和平均处理时间 ig. 6 Comparison of the response time and process time at different sizes of slide window 225 从图6可知,STPM模型在滑动窗口大小増加的情况下,处理时间的増长远低于SPM 模犁这是由于SPM模型中的单次处理均需要与仝局窗口内的数据进行测试,而STPM模型 只考虑局部数据。但是不足之处是在STPM模型中通信时间开销比SPM模型中増长吏快 423并行度大小对查询性能的影响 实验过程中,对基于STPM模型的査询算法与基于SPM模型的算法,在数据维度大小 230为2,并行度为4,8,16,32,滑动窗凵大小为200K条件下,进行不确定数据流的并行 Skyline 查询的性能对比,如图7所示。 a SPM Response T ime &.-. SI PM Response I ime [=--3- SPM Process Time ■ STPM Process Time 8 图7不同并行度下单次查询的平均响应时间和平均处理时间 Fig 7 Comparison of the response time and process time at different degrees of parallelism 235 从图7可知,随并行度的増加,SPM模型的査询效率的提升逐渐减少而STPM模型在 处理效上提爪较多,但是受到通信开销的影响导致整体响应吋间的提并不明显。这个结 果反映出解决通信丌销是STPM模型还需要进步改进的地方。 5总结 为了在确定数据流并行 Skyline查询的过程中减少查询响应时间、提高可扩展性,本 240文提岀了分步并行模型和基于分步并行模型的高效可扩展的查洵算法。实验表明基于分步并 行模型的査询算法具有良好的性能和可扩展性。 山国武获论文在丝 http:/www.paper.edu.cn 未来的工作主要集中在三个方面:1)将基于本文提岀的算法硏究支持不确定数据流 p- skyline并行处理的剪枝算法,减少通信开销对算法的影响:2)将研究更细粒度的并行化 例如对于并行节点內支配关系测试的并行化等;3)研究攴配关系图算法在新型 Skyline查询 245中的应用,如子空间不确定 Skyline查询, Top-k Skyline查询等。 参考文献]( References) [1] Zhang Wenjie, Lin Xuemin, Pei Jian, et al. Managing uncertain data: Probabilistic approaches[A]. Proceedings The 9th International Conference on Web-Age Information Management, WAIM 2008[C]. Piscataway, NJ: IEEE 2008.405-412 250 [2 Aggarwal Charu C, Yu Philip S. A survey of uncertain data algorithms and applications[]. IFEF Transactions on Knowledge and Data Engineering, 2009, 21(5): 609-623 3 Cormode graham, Garofalakis Minos. Sketching probabilistic data streams[A]. Proceedings of the ACM SIGMOD international conference on Management of data[C]. New York, NY: ACM, 2007. 281-292 [4] Borzsony S, Kossmann D, Stocker K. The skyline operator[A]. Proceedings-International Conference on Data 255 Engineering[C]. Piscataway, NJ: IEEE, 2001. 421-430 [5]魏小娟,杨婧,李翠平,等. Skyline查询处理[J.软件学报,208,19(6):1386-1400 [6]王意洼,李小勇,祁亚斐,等.不确定数据查询技术研究[.计算机研究与发展,2012,49(7):1460-1466 [7] Wang Yijie, Li Xiaoyong. Li Xiaoling, et al. A survey of queries over uncertain data[J]. Knowledge and Information Systems(KAIS), 2013, April: 1-46 260 [8] Tao Yufei, Papadias Dimitris. Maintaining sliding window skylines on data streams[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(3): 377-391 l刂孙圣力,戴东波,黄震华,等.概率数据流上 Sky line査询处理算法山电子学报,2009,37(2):285-293 [10] Zhang Wenjie, Lin Xuemin, Zhang Ying et al. Probabilistic skyline operator over sliding windows[A Proceedings-International Conference on Data Engineering c]. Piscataway, NJ: IEEE. 2009. 1060-1071 265 [1 1 Ding Xiaofeng, L,ian Xiang, Chen Lei, et al. Continuous monitoring of skylines over uncertain data streams Information Sciences, 2012, 184(1): 196-214 「12]王意洁,李小勇,炀永滔,等.不确定 Skyline查洵技术研究「.计算机研究与发展,2012,49(10): 2045-2053 [13 Pei Jian, Jiang Bin, Lin Xuemin, et al. Probabilistic skylines on uncertain data: Model and 270 bounding-pruning-refining methods[J] Journal of Intelligent Information SystemS, 2012, 38(1): 1-39 [ 14] Bartolini llaria, Ciaccia Paolo, Patclla Marco. The skyline of a probabilistic rclation [J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(7): 1656-1669 15]王晓伟,黄九鸣,贾焰.分布式不确定数据上的慨率 Skyline计算「J.计算机科学与探索,2010,4(10): 951-961 275 6] Ding Xiaofeng, Jin Hai. Efficient and progressive algorithms for distributed skyline queries over uncertain data[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(8): 1448-1462 7]王广东,王意洁,李小勇,等.不确定数据流上的并行 Skyline查询算法门_计算机科学与探索,2012, 6(12):1116-1125 [18 Yang Yongtao, Wang Yijic. Towards estimating cxpcctcd sizcs of probabilistic skylines[]. Scicncc China 280 Information Sciences, 2011, 54(12): 2554-2564

...展开详情
试读 9P 论文研究-不确定数据流上高效可扩展的并行Skyline查询算法 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_39840588 如果觉得有用,不妨留言支持一下
2019-08-19
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
上传资源赚积分or赚钱
最新推荐
论文研究-不确定数据流上高效可扩展的并行Skyline查询算法 .pdf 10积分/C币 立即下载
1/9
论文研究-不确定数据流上高效可扩展的并行Skyline查询算法 .pdf第1页
论文研究-不确定数据流上高效可扩展的并行Skyline查询算法 .pdf第2页

试读结束, 可继续读1页

10积分/C币 立即下载 >