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

摘要：

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

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

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金61173165，61300187，61370198，61370199，U1433124；中央高校基本科研业务费专项资金31322013044，31322013029，3132014325，3132013335；辽宁省教育厅科学研究一般项目L2015092，L2014492，L2014283，L2014191；江苏省未来网络创新研究院未来网络前瞻性研究项目资助课题

在线出版日期：2016-03-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：215-222