面向高效并行Skyline计算的数据划分方法

• 作者: 商海川 赵翔
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 并行Skyline 数据划分 排列模型 可扩展性
• 年，卷（期）: 2020,（11）
• 页码范围: 2050-2066
• 页数: 17页
• 分类号: TP311
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2020.02050

摘要

Skyline计算是数据管理领域长久以来的一个研究重点和热点.给定一组多维的数据点,Skyline算子从中筛选出在所有维度上都不被其他点支配的数据点;Skyline算子的处理过程称之为Skyline计算.Skyline算子使得用户可以在较小规模的Skyline结果集上选择自己感兴趣的对象,而无须关心那些已经被过滤掉的对象.因此,Skyline计算在多目标决策、数据可视化分析、用户偏好查询等方面应用广泛,典型的应用任务包括但不限于商业营销策略分析,产品能力横向评估等.随着大数据时代的到来,以及分布式网络系统的深入应用和基于云计算平台解决方案的快速发展,各类应用领域数据规模的快速增长已经成为一个关键性技术挑战,面向大规模数据集的并行Skyline算子应运而生,以部分解决大数据给Skyline计算困难;同时,并行Skyline计算的相关研究近年来备受学术界和工业界的广泛关注.由于缺乏关于整个数据集的全局分布信息,并行Skyline计算的高效处理面临着巨大的技术挑战.一般认为,并行Skyline处理的计算框架通常包含三个主要步骤:(1)合理划分给定的大数据集;(2)利用本地计算资源在每个数据分块上分别计算局部Skyline;(3)合并局部Skyline最终形成全局Skyline.其中,针对后两步——计算局部Skyline和合并局部Skyline的现有算法较多,相关研究相对成熟;相较而言,第一步上的相关研究工作则较少,但其效果却直接决定了整体计算的并行化程度,进而能够影响并行计算系统的整体性能.具体地,第一步需要考虑两方面的准则:(1)各个分块上的计算负载是否均衡;(2)如何减小每个分块上局部Skyline的基数.然而,无论采用基于随机划分还是基于网格的方法,现有算法均只能满足上述两个准则之一,不能两全其美.针对该问题,研究探索了如何利用概率模型估计Skyline基数的期望,该概率模型将已有研究的相关结论纳入到了一个统一的框架中.接着,据此提出了一种新的基于排列的数据划分方法,它通过简单的数据点映射即可实现负载均衡,同时生成小于现有其他方法的Skyline候选点集.在理论研究的坚实基础上,在大型人工和真实数据集上实验验证了所提模型和方法的有效性;换言之,在大规模实验研究中,所提方法显著提高了并行Skyline算子的执行效率,在绝大多数参数设定下的表现都优于现有其他同类算法.