基于时间序列的Global Skyline并行算法

李媛媛, 曲雯毓, 栗志扬, 季长清,3, 吴俊峰,4

(1. 大连海事大学信息科学技术学院, 辽宁 大连 116026; 2. 大连交通大学软件学院,

辽宁 大连 116028; 3. 大连大学物理科学与技术学院, 辽宁 大连 116622;

4. 大连海洋大学信息工程学院, 辽宁 大连 116023)



基于时间序列的Global Skyline并行算法

李媛媛1,2, 曲雯毓1, 栗志扬1, 季长清1,3, 吴俊峰1,4

(1. 大连海事大学信息科学技术学院, 辽宁 大连 116026; 2. 大连交通大学软件学院,

辽宁 大连 116028; 3. 大连大学物理科学与技术学院, 辽宁 大连 116622;

4. 大连海洋大学信息工程学院, 辽宁 大连 116023)

摘要：Global Skyline 查询是Skyline查询的一种变种,它和动态Skyline查询、反Skyline查询关系密切,已被广泛应用于多目标决策、网络监控、数据挖掘等方面。随着数据的积累,传统集中式的Skyline查询已经不能满足大数据的处理要求。为了高效解决大规模的基于时间序列的数据处理难题,提出了基于MapReduce框架并行的Global Skyline Cell查询算法。首先,通过对实际应用需求进行分析,本文提出了基于时间序列数据Skyline查询的时间倒排索引模型;并提出了Global Skyline格概念,利用格间的支配关系进行粗粒度高效剪枝,避免了大部分的无效运算;其次查询点将数据空间分割成不同象限,基于各象限进行轮询,实现了Global Skyline 格的查询,在此候选结果中得到Global Skyline点,为下一步实现动态Skyline和反Skyline查询奠定基础。最后,我们在Hadoop集群环境中实现了该算法。实验结果表明,该算法能有效解决基于时间序列的大规模数据Skyline查询的时间和空间矛盾,能够满足实际应用需求。

关键词：Global Skyline查询;MapReduce;大数据;时间序列

0引言

Skyline查询问题又叫Pareto最优或极大向量问题[1],是从数据集中查找感兴趣的点,这些点不被其他点所支配。……