论文部分内容阅读
随着科学技术的不断发展,传感器监控、物联网、云计算等许多新的应用随之产生,这些应用产生的是时变、无限、高速、不可预测、持续到达的数据流,需要在线无阻塞处理。而传统的数据处理算法主要是针对持久的、有限的,确定性的数据,因此传统数据处理算法的局限性以及计算机资源的有限性已经成为处理高速数据流的瓶颈。本文以高速数据流作为分析处理对象,研究更适合处理高速数据流的算法,主要涉及数据流间的窗口连接以及数据流间的相关性分析,可应用于交通信息管理。研究工作主要分为以下三个方面:1.针对大规模不确定数据流并行连接所存在的速度问题,以查询套牌车为背景,在内存无溢出环境下,提出了不确定数据流并行连接算法。一方面,提出了多线程实时删除和定时删除两种算法。这两种算法均设计了一个分发线程和多个处理线程,分发线程主要负责数据预处理以及分发数据;处理线程负责数据的插入、比较和连接,引入了哈希索引、链表排序等优化措施加快线程处理速度。这两种算法的不同之处主要是删除过期数据的时间点不同。另一方面,本文利用Oracle Timesten设计了内存数据库算法。实验显示本文提出的算法的处理速度比内存数据库Timesten速度提高约2-8倍,能够满足实时监控交通套牌车的需求。2.针对大规模不确定数据流并行连接所存在的内存消耗问题,以查询套牌车为背景,在内存溢出环境下,提出了窗口一半算法以及小于概率算法,以解决在内存溢出的问题。算法始终将最近到达的大概率数据留在内存中,同时将小概率或窗口部分数据写入硬盘,这样保证实时到来的数据流与链表中的数据连接后,可以优先输出可能性大的高概率数据。等到数据流速度变慢或者停止时,再将小概率数据调入内存做进一步处理。实验证明,算法可以优先输出大概率数据,能够满足实际需要。3.针对多维数据流相关性分析提出一种新颖的基于基窗口的在线典型相关分析算法Base_win_CCA。算法删除原始数据,仅保留每条数据流基窗口内大量观察值的统计量作为基统计量,多个滑动窗口范围的统计量可利用基统计量增量计算得到。算法克服了目前多维数据流求单一窗口内相关性和需要保留大量原始数据的缺点,比较灵活,而且运算结果精确。理论分析和实验结果表明算法在基窗口越大,相关性查询窗口越大,数据流条数越多,查询用户越多的情况下能体现出优越的性能。