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

摘要

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

关键词