海量时间序列数据处理的关键技术研究

发布时间：2018-01-06 06:35

本文关键词：海量时间序列数据处理的关键技术研究　出处：《大连理工大学》2017年博士论文　论文类型：学位论文

【摘要】：近年来,传感器网络、物联网、云数据中心和移动互联网等新技术的快速发展使时间序列数据呈现了爆炸式增长,而时间序列数据具有其他类型数据所不具备的特点。首先,时间序列数据规模非常大,同时又是以数据流的形式源源不断产生,其计算面临着数据流频率高、序列过长和数据量过大而导致响应时间过长的问题;其次,时间序列数据还具有维度高、特征多样化等特点,其索引划分精度和处理效率需进一步提高。在时间序列数据处理平台中还有大量问题需要解决,针对离线批处理、在线计算和数据流实时处理三种典型的大数据处理模式,本文分别选取了基于MapReduce的海量时间序列的相似性连接、基于HBase的时间序列数据的皮尔森相关系数(下文简称"相关系数")估算和实时数据流多连续查询共享三个关键问题进行深入研究;同时针对海量时间序列数据处理平台的Hadoop集群,深入研究了集群网络调度问题。具体创新如下:(1)针对海量时间序列的相似性连接问题,基于MapReduce提出了索引结构相似性连接树SJT(Similarity Join Tree)。SJT可以通过结点之间的位置关系记录分区阶段产生的计算量,在Reduce阶段利用这些已有的计算量剪枝大量精算阶段的计算量,以提高计算效率;为保证分区负载均衡,扩展F-M(Fiduccia-Mattheyse)算法,设计了基于SJT的图分区算法,该方法可以保证分区之间传输的数据量最小。实验证明,提出的方法优于当前的最好的方法ClusterJoin和MAPSS。(2)为了提高在HBase上实时计算长时间序列相关系数的效率,提出了一种相关系数上下界的快速估计算法DCE。为了进一步减少I/O代价,对DCE算法进行扩展,提出了 ADCE算法,该算法通过维护一种多层摘要数据,能够通过迭代对相关系数进行估计。实验证明,提出的算法能够快速计算长时间序列(如:108、1010的长度)的相关系数。(3)针对实时数据流聚集运算,提出基于窗口的多连续查询的协同聚集模型,可以在窗口中实现结果共享,以避免重复的聚集操作。已有的聚集共享方法往往受到窗口步长限制,而本文提出的多连续查询环境下基于步长和结果的窗口重用机制,可以通过一系列逐渐减少的多值来简化聚集过程,每一步都缩减操作步骤,并完成结果共享。提出了 feed语义来标准化共享全过程,并提出compose-and-declare框架来处理数据共享逻辑。实验证明,提出的方法比当前的最好方法TriWeave性能有所提升。(4)为了减少时间序列数据处理作业的完成时间,基于Hadoop集群,通过实时监控并获取应用层的网络流信息,提出了基于作业的优先级调度方法。提出Flow-based和Spray两种利用等价多路径的方法,并在Fat-Tree拓扑中实现负载均衡。实验证明,提出的调度方法可以提升shuffle阶段作业执行效率,尤其是减少了最高优先级作业的网络传输时间。
[Abstract]:In recent years, with the rapid development of sensor network, Internet of things, cloud data center and mobile Internet, time series data has been explosive growth. But the time series data has the characteristic which other types of data do not have. First, the time series data scale is very large, at the same time the time series data is produced continuously in the form of the data stream, its computation faces the high frequency of the data flow. Too long sequence and too large amount of data lead to the problem of too long response time; Secondly, the time series data also has the characteristics of high dimension and diverse features, its indexing accuracy and processing efficiency need to be further improved. There are still a lot of problems to be solved in the time series data processing platform. Aiming at the three typical big data processing modes of off-line batch processing, on-line computing and real-time data flow processing, this paper selects the similarity connection of massive time series based on MapReduce. There are three key problems in the estimation of Pearson correlation coefficient (hereinafter referred to as "correlation coefficient") of time series data based on HBase and multi-continuous query sharing in real-time data flow. At the same time, aiming at the Hadoop cluster of magnanimous time series data processing platform, the scheduling problem of cluster network is studied in depth. The concrete innovation is as follows: 1) the similarity connection problem of mass time series is discussed. An index structure similarity join tree SJT(Similarity Join tree based on MapReduce is proposed. SJT can record the amount of computation generated during the partition phase through the location relationship between nodes. In the Reduce stage, these existing calculations are used to prune a lot of calculations in the actuarial stage in order to improve the calculation efficiency. In order to ensure partition load balance and extend F-MN Fiduccia-Matthew algorithm, a graph partitioning algorithm based on SJT is designed. This method can ensure the minimum amount of data transferred between partitions. The proposed method is superior to the current best methods ClusterJoin and MAPSS. 2) in order to improve the efficiency of real-time calculation of correlation coefficients of long time series on HBase. A fast estimation algorithm for the upper and lower bounds of correlation coefficients is proposed. In order to further reduce the I / O cost, the DCE algorithm is extended and the ADCE algorithm is proposed. By maintaining a multi-layer summary data, the algorithm can estimate the correlation coefficient by iteration. Experiments show that the proposed algorithm can quickly calculate long time series (such as: 108). The correlation coefficient of 1010))) for real-time data stream aggregation, a window-based multi-continuous query based cooperative aggregation model is proposed, and the results can be shared in the window. In order to avoid repeated aggregation operations, existing aggregation sharing methods are often limited by window step size, and the window reuse mechanism based on step size and result is proposed in this paper. The aggregation process can be simplified by a series of decreasing multi-values, each step can reduce the operation steps and complete the result sharing. A feed semantics is proposed to standardize the whole process of sharing. The compose-and-declare framework is proposed to deal with the data sharing logic. In order to reduce the time series data processing job completion time, the proposed method is based on Hadoop cluster. Through real-time monitoring and obtaining the network flow information of the application layer, a job-based priority scheduling method is proposed, and two equivalent multipath methods, Flow-based and Spray, are proposed. Load balancing is realized in Fat-Tree topology. Experiments show that the proposed scheduling method can improve the efficiency of job execution in shuffle phase. In particular, the network transmission time of the highest priority jobs is reduced.
【学位授予单位】：大连理工大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：O211.61

【相似文献】