基于时间关联性的数据流乱序处理技术

摘要

随着互联网和大数据技术的不断发展与应用，产生了源源不尽的数据流。数据流的产生具有无限性、连续性、动态性和实时性，因此对数据流的分析处理要求快速有效地获取结果，以便保证分析结果的时效性。但是，数据流上的乱序问题会导致数据流处理结果的丢失，给数据流的分析处理带来了巨大挑战。
　　在对数据流的分析研究中，数据流间相似性连接是一项重要基础操作，常用于数据流的挖掘和分析。乱序问题严重破坏了数据流处理结果的完整性。本文研究基于滑动窗口语义下的数据流相似性连接问题，探讨质量驱动下的乱序数据流连接处理方法与技术，开展了以下方面的研究工作:
　　(1)提出一种质量驱动的乱序数据流连接处理技术QJoin。该技术采用缓存技术和对称连接策略保证流元组能被即时分析处理，以降低流元组的平均等待时延，提升基于滑动窗口语义的乱序数据流连接处理的处理速率;基于质量驱动的理念，通过在临近阶段连接处理过程中收集统计数据来优化缓存的大小，使得在满足用户结果质量要求的前提下，通过降低历史数据的内存缓存量，尽可能保证迟到元组的连接处理完整性，从而降低系统的内存开销。真实数据集上的实验结果表明，与传统的数据流乱序处理技术MP-K-slack相比，QJoin技术在满足用户结果质量要求的同时，不仅能够保证数据流的流元组被即时分析处理，还显著降低了内存使用开销。
　　(2)分析数据流速的动态变化特性，针对流速连续增大造成系统持续过载的问题，在QJoin缓存受限的基础上提出了一种系统资源降载策略。该策略在数据流速过高时，基于时间关联性适当地把冗余的元组过滤掉，以此来降低系统负荷，提高对系统持续过载问题的应对能力。真实流数据集的动态变化实验结果表明，基于QJoin的系统资源降载策略能够有效应对数据流速持续增大时系统持续过载的行为，提升了QJoin技术的性能。
　　本文从适应数据流应用的即时处理和用户结果质量需求的角度，提出了一种新的乱序数据流连接处理技术，有效降低了系统内存开销，提高了数据流相似性连接问题的查询效率，为基于滑动窗口语义的乱序数据流相似性连接问题处理提供了可行有效的解决方案，可以广泛地应用于视频流对象跟踪、趋势监控和谐度分析等领域。论文的研究具有一定的科学意义和应用价值。

目录

声明

摘要

第一章 绪论

1．1 研究背景及意义

1．1．1 研究背景

1．1．2 研究意义

1．2 国内外研究现状

1．2．1 数据流乱序处理技术

1．2．2 基于时间关联性的数据流相似性

1．2．3 数据流连接的降载策略

1．2．4 已有研究工作分析和结论

1．3 本文的主要工作及组织结构

1．3．1 主要工作

1．3．2 论文的组织结构

第二章 相关知识概述

2．1 数据流定义

2．2 基于滑动窗口语义的数据流相似性连接

2．3 数据流乱序定义

2．4 数据流降载策略

第三章 质量驱动的乱序数据流连接处理技术QJoin

3．1 问题的分析与提出

3．2 QJoin技术的设计思想

3．3 对称连接

3．4 基于用户质量的缓存自适应

3．4．1 L周期用户质量期望

3．4．2 L周期受缓存影响的质量

3．5 QJoin技术的算法描述

3．6 实验与性能分析

3．6．1 实验环境设置

3．6．2 实验结果与分析

3．7 本章小结

第四章 基于时间关联性的降载策略

4．1 问题分析与提出

4．2 基于时间关联性的降载策略设计与实现

4．2．1 过载检测

4．2．2 降载策略设计与实现

4．3 实验结果与性能分析

4．3．1 实验设置

4．3．2 实验结果与性能分析

4．4 本章小结

5．1 研究工作总结

5．2 展望

参考文献

致谢

攻读学位期间发表论文情况