数据流连续查询处理技术的研究

数据流查询处理技术的研究是目前数据库研究领域的热点问题.传统的数据库技术不能处理诸如网络监测、传感器网络、股票分析等应用中所生成的新型数据,即数据流.数据流作为一种新的数据形态,不同于传统的静态数据,具有连续快速、短暂易逝、规模宏大和不可预测的特点;其研究核心是在一个远小于数据规模的有限存储空间迅速获得近似查询结果.综述关于数据流查询处理技术的研究成果,主要介绍数据流模型、查询的特征、数据流近似查询操作算法的实现以及数据流系统中的查询处理方法.     

数据流持续查询系统的窗口语义研究

在需要处理数据流的应用系统中，数据流的达是持续的、无界的，传统对静态数据库进行分块查询处理的方式已不再适应这种数据流的无穷性．本文针对数据流持续查询应用的不同场合，提出在查询中使用滑动窗口、带符号的数据流及断言窗口机制，使传统的查询处理加上这些机制后能适应数据流的查询处理，     

数据流处理系统的负载控制策略研究

在高速网络数据流查询处理系统中,数据到达可能是突发性的,对数据流的实时查询处理要能适应数据流的特性和网络的波动环境,应用闭环控制理论进行系统负载控制,充分利用系统资源,在系统过载时降低存储需求,提高适应性和精确度.     

支持非等值连接的分布式数据流处理系统

实时处理的分布式数据流系统在当今大数据时代扮演着越来越重要的角色.其中,连接查询是大数据分析处理中最为重要且开销较大的操作之一.然而,由于现实应用产生的数据普遍存在倾斜分布现象,加之数据流本身的无界性与不可预知性,给在分布式数据流系统上进行连接查询处理提出了严峻的挑战.目前工业界较为主流的数据流系统处理连接查询的通用性较低,没有提供专门针对连接操作的接口;学术界推出的数据流连接查询原型系统虽然提供了接口,但大多面向等值连接,或仅能支持部分theta连接,且存在资源开销大、负载均衡性能低等问题.本文对比分析三种典型数据流系统,将基于Join-Matrix的连接处理技术与Storm系统相结合,设计并实现了通用的、可支持任意连接查询的数据流处理系统.实验展示了本文设计的系统具有更加良好的吞吐量与资源优化表现.     

基于混合处理模型的乱序数据流分布式聚合查询处理技术

为了解决现有的乱序数据流聚合查询处理技术不能在降低查询处理延迟,同时保障聚合查询结果的最终正确性的局限性问题,本研究设计了混合嵌入分布式流处理模块和分布式批处理模块的乱序数据流分布式聚合查询处理技术。该技术一方面基于用户给定的结果质量,限制自适应地优化流处理模块所用的缓冲区大小,从而尽可能降低流处理的查询处理延迟;另一方面基于备份于分布式数据存储系统的历史流数据,并以批处理的方式实现对极其晚到流元组的查询处理,从而保障聚合查询结果的最终正确性。基于真实的乱序数据流数据集对该技术进行测试分析表明:该技术在平均查询处理时延、查询结果精度和系统可扩展性方面,比目前最好的基于缓存的乱序数据流处理技术均具有显著优势。     

数据流管理系统关键技术研究

传统数据库系统用于需要持久稳固的数据存储和复杂查询的应用,然而近几年许多的应用证明这种数据模式和查询范例是不适合的,如传感器数据位置跟踪、工厂装配线管理、金融证券管理、Internet流量监控、Web使用日志、电话呼叫记录、和事务日志的在线分析等,在这些应用背景中信息按照数据值序列的形式自然产生,都需要及时地处理大规模的潜在快速的异步的数据流.本文回顾近来数据流管理系统领域的相关工作和流项目的研究情况;分析了连续查询处理的新需求和挑战;重点研究包括数据模式,系统结构,连续查询语言,调度方法,相关算法和查询评价等关键技术.     

无线传感器网络中数据流聚集的预处理

提出了一种基于无线传感器网络数据流聚集的预处理算法。传感器结点将其在一段时间内采集到的信息当作一个数据流,由此组成数据流上的查询集合,为了得到对于给定查询的结果,结点采用预处理的算法在查询集合中选择出最有效的时间段信息,并把该段时间内的数据发给路由上其他结点进行进一步处理。提高了网络结点感知效率和数据精确度。     

一种基于混沌理论的数据流连续聚集查询预测算法

为了有效地预测聚集查询的未来聚集值,提出了一种基于混沌理论的数据流连续聚集查询预测未来聚集值算法——CSPA算法.数据流看作是以数据到达时间为序的一个时间序列,借鉴传统时间序列分析技术探讨了连续聚集查询的未来聚集值预测问题,但由于数据流序列与传统时间序列在时间间隔和数据集的处理上存在很大差别,于是采用流滑动窗口技术加以处理.其次,针对目前数据流聚集查询预测领域已有的一些研究结果都未考虑流数据内在的复杂非线性动力学特征对预测的影响问题,该算法又利用了混沌理论中的局域预测思想解决了这一不足.实验结果表明,利用该算法进行预测具有很好的准确性.     

面向社交数据流连续查询的基准评测

社交数据流上的连续查询处理具有广泛的应用,但其处理技术仍不成熟.本文对社交数据流上的连续查询问题进行建模,定义数据特征、负载类型与分布,以及性能测度.在此基础上,提出一个面向该问题的基准评测.该工作对社交数据流处理应用的系统选型、相关查询处理技术性能比较具有重要意义.     

基于直方图的数据流降载策略研究

提出了基于直方图的降载策略,能很好地减缓在过载发生时系统性能的下降.降载的目标在于删除过载数据的同时尽可能地保持数据流的特征.为了处理大量被延迟的数据,构建了一种塔形矩阵的数据存储结构,利用其对过载数据分桶,每桶提取一个代表数据并删除该桶中其余数据,将每个桶的代表数据组成新的数据流参与查询操作.实验结果表明:这种降载方法能有效减少系统负担,生成的新数据流参与数据流查询后所得查询结果错误率较低,其性能优于其他已有算法.     

数据流窗口查询语义的局限性及改进方法

在数据流处理系统普遍使用滑动窗口查询模型来解决数据流的持续查询问题.对一些特殊的查询类型,在使用滑动窗口查询时无法完全达到查询要求,通过引入条件窗口对滑动窗口模型进行更一般化的扩展和改进,可以解决滑动窗口语义在处理这一类型查询中的局限性.     

面向网络数据流的持续查询

有别于传统的存储型数据静态查询,构造了一种对网络数据流进行持续查询的模型．该模型提供了映射和转化机制,兼容了数据流“时序”概念和传统数据库中的“关系”概念。     

共享连接结果的连续查询处理

深入研究了适合数据流连续查询处理的Shared PushDown,PullUp和Filtered PullUp三种可共享连接结果的策略.通过理论分析和实验证明,在数据流的连续查询处理中,PullUp策略性能较低,而Filtered PullUp和Shared PushDown策略各占优势.Filtered PullUp处理简单,消耗内存相对较少.而Shared PushDown增加内存使用,但在注册查询的选择因子覆盖较少时有一定优势.考虑到处理的方便,一般情况下Filtered PullUp是适合数据流连续查询处理的最佳方案.     

基于XPush自动机的XML动态查询过滤优化

大数据中存在大量非结构化数据,在XPush自动机的基础上,考虑XML数据流的动态查询过滤,提出一种基于合并自动机的方法递增的处理XML数据流,该方法对于现实应用中极为有用,可以动态满足用户的需要和查询过滤的要求.本文提出的集成XPush自动机的模型,分自动机模块和控制模块两个部分来进行动态查询过滤,使用有序的哈希键值更加有效的实现查询系统的动态更新,通过分离进程和增加新的查询处理两方面来实现查询的动态性.最后实验证明集成XPush自动机在查询要求发生改变的不同情况下较原先的XPush自动机都具有较低的过滤时间代价.     

连续查询的运算符调度方法

在连续查询的数据流应用系统中,需要处理连续的大容量数据元组,由于有限的硬件条件限制,会出现未能及时处理的元组,导致内存耗尽的问题和输出延迟等问题,通过查询计划中运算符的调度方法分析,在不同的场合中综合运用发挥不同方法的优势,可以做到降低内存需求和输出延迟.     

一种高效的不确定数据流Top-K 查询算法

在传感器网络、RFID等各种应用中会产生大量不确定性数据,有效的Top-K查询处理是不确定性数据管理中一项重要技术。针对已有的Top-K查询没有很好地结合元组的分值和不确定性,在分析不确定性数据模型和可能世界模型的基础上,定义了不确定数据流元组的查询语义。设计并实现了一种有效的Top-K查询算法。该算法按照元组的得分值进行降序排列,概率值最高的前K个元组集合就是Top-K的查询结果,实验结果表明,与CSQ和SCSQ算法相比,更具高效性和实用性。     

移动环境中的位置依赖连续轮廓查询

针对移动环境中查询点快速移动时连续、高效输出给定搜索区域数据轮廓的问题,提出一种位置依赖连续轮廓查询算法(LDCS).该算法结合数据流技术,首先使用R树快速更新查询数据,然后利用两次连续计算时搜索区域的重叠性构造被动数据流,并对新增和失效数据分别进行处理,从而连续输出轮廓.由于充分利用了已有结果,LDCS的计算量较传统算法有大幅下降.实验结果表明,LDCS特别适合计算频度要求较高的场合,与基于网格索引的算法相比,时间效率随着数据集规模的增大显著提升.     

RFID数据流管理关键技术

新一代传感器和RFID(无线射频识别)技术为人们提供了强大的感知、理解并管理世界的能力,同时RFID数据具有不确定性、冗余性、蕴含时空性、需要在线处理等特点,也为数据管理提出了许多挑战,本文回顾了RFID数据管理的研究发展现状,从数据流连续查询、物化视图推导规则、复杂事件处理等角度分析了RFID数据管理涉及到的几种关键技术,最后介绍一种数据流驱动的RFID复杂事件处理系统(CodEye Event Processor)的设计思想,将RFID事件查询设计成复杂连续查询,能够有效捕捉并处理复杂RFID事件.     

一种数据流上基于截止期的多查询过载预测模型

为保证数据流上查询处理的实时性要求,定义了截止期作为连续查询的实时性约束,提出了一种数据流上基于截止期的多查询过载预测模型.模型预测的过载点给出了能够保证数据流系统内所有查询满足各自截止期的临界情况.在多查询环境下,通过找到某一查询作为截止期瓶颈,使得该查询处理结束后剩余查询的处理能力正好大于系统的输入流速,从而计算出过载点.仿真实验结果证明,该模型预测出的过载点能够保证所有查询满足各自的截止期,并且预测算法具有良好的准确性和计算复杂性.     

基于层次模型的kNN查询处理算法

针对当前基于二级网络模型的数据流k-最近邻(kNN)查询中网络流量大、查询结点负载重的问题,提出了一种新的网络模型,将二级网络模型扩展到更通用的层次网络模型。该模型改进了查询算法,在远程节点与查询节点间布置多个中间节点,以处理数据,降低网络数据传输量,减小查询结点的负载。理论分析和数值实验表明新算法能取得较好的结果。