分布式数据流查询处理若干关键技术的研究

《分布式数据流查询处理若干关键技术的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分布式数据流查询处理若干关键技术的研究摘要随着大规模网络的发展和Web的广泛应用，在网络监控、入侵检测、传感器网络、通讯数据管理、股票分析等应用领域中产生了一种新型数据一数据流(或流数据)，如关系元组、传感器读入值、网络性能参数、电话记录和股票交易数据等。与传统数据库应用模型不同，数据流模型具有以下特点：(1)数据连续、实时到达；(2)数据量大、无限制并且难以预测；(3)数据一经处理，除非特意保存，否则不能被再次取出处理，即一次性处理(one-pass)，或者再次提取数据的代价昂贵。如何对这些流数据进行存储、查询处理已经成为当前国际数据库研究领域的热点问题。在许多实际应用中，如决策支持系统

2、、查询优化等，用户并不需要获得确切值，而只需要一个近似值。因此，数据流分析和管理的核心是设计一次扫描算法，即在一个远小于数据规模的内存空间里不断更新一个代表数据集的结构一概要数据结构，使得在任何时候都能够根据这个结构快速实时地获得近似查询结果。如果流的长度为N，则概要数据结构的规模大小不超过0(polylog(N))，并且处理流上每一组数据的时间不超过0(polylog(N))。传统数据库中的查询主要是一次查询，即系统根据当前数据集合的快照给出查询结果，并将该结果返回给用户。而数据流的查询为连续查询，即查询随着新数据的到来而不断的返回查询结果。连续查询是数据流上特有的操作，具有长期运行的特

3、点。由于数据流环境中的数据集不是静态的，而是不断有数据插入和更新。用户需要的也不是在某个时刻的静态查询结果，而是对整个数据流的一个动态监测，随着数据流的不断变化持续地产生查询结果。现有的数据流的研究主要为集中式的流数据系统，而数据流的本质是分布式的，越来越多如传感器网络、数据通讯、Internet流量分析和Web日志等的大量数据都来自不同的远程数据源，因此，需要构建分布式数据流查询处理的中间件以支持上述各种应用。P2P技术利用互联网的终端机来建立一个庞大的分布式计算网络，并对迅速涌出的大量信息进行处理。这些计算机(即对等点)在网络中处于同等的地位，各自拥有独立的网络自主权，以解决把所有的计

4、算压力全部加在服务器一端所造成的瓶颈问题。P2P以其可扩展性、通信负载平衡，资源的高利用率以及由基于内容的路由机制所提供的动态变化的适应性等特性成为构建中间件的良好平台，以便在减少网络带宽和网络连接所消耗的计算资源情况下，提供快速有效的数据流查询处理的实时响应。本论文以分布式数据流为主要研究对象，分析了国内外的研究现状，从目前存在的问题和不足出发，研究数据流基于时间变化的特性，监测当前流入的数据，探索数据流变化的表示与建模方法，分析数据进化和变化的趋势，并对未来流入的数据进行预测。在大规模分布式环境中，研究时间和空间复杂度最小的分布式数据流查询处理和挖掘算法。一方面，研究小波分解技术，利用

5、小波系数的近似处理方法构建和维护小波直方图，以获得好的精确度，并且将其扩展到多维直方图的构建和维护，解决传统的直方图技术难以解决的问题，并利用小波系数构造数据流集的概要，建立一个复合索引结构来响应各种查询；还研究小波多分辨分析思想，构造一种小波神经网络模型，解决了传统神经网络中隐层节点数难以确定的问题，初步建立分布式时间序列数据流的预测模型。另一方面，运用草图技术解决在数据流上的聚集查询等难点问题。研究分布式数据流中频繁项的发现算法，通过设置精确梯度来减少通信开销，实现数据流查询的实时响应。同时，以P2P环境的Chord网络结构和协议为平台，研究分布式数据流挖掘和及时响应查询处理的中间件，

6、探索在对等计算系统中提供流数据的近似查询功能所涉及到的数据和查询路由、定位与查找、索引及数据流概要的映射等关键技术问题。具体来说，本论文的主要创新点在于以下四n个方面：(1)研究了基于小波技术的分布式数据流的查询处理算法。首先通过离散小波变换理论与DWT分解哈尔小波方法获得小波系数，然后分析了数据流的计算模型，形式化了数据流的查询模型。在此基础上，提出了一种新的方法来构造数据流集的概要，建立一种复合索引结构来处理内积查询和相似查询。此外，还结合小波神经网络WNN良好的时频局部化性质以及神经网络的自学习功能，初步建立适应于时间序列数据流的预测模型。(2)研究了基于草图技术的分布式数据流的聚集

7、查询算法。首先分析了基于草图的近似处理算法，然后利用随机技术，在数据流到达时实时计算数据的伪草图概要。在此基础上，提出新颖的草图分割技术，通过属性值域的智能分割来减小分割后的自联接规模以及为每个分割的独立草图公平地分配存储空间两个方面来保证近似估算质量。(3)研究了大规模分布式数据流中频繁项的发现算法。通过对单个数据流频繁项的发现算法的分析，形式化地定义了基于时间点的分布式数据流频繁项的发现问题。并提出了基于LossyC