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

论文摘要

随着大规模网络的发展和Web的广泛应用，在网络监控、入侵检测、传感器网络、通讯数据管理、股票分析等应用领域中产生了一种新型数据—数据流（或流数据），如关系元组、传感器读入值、网络性能参数、电话记录和股票交易数据等。与传统数据库应用模型不同，数据流模型具有以下特点：（1）数据连续、实时到达；（2）数据量大、无限制并且难以预测；（3）数据一经处理，除非特意保存，否则不能被再次取出处理，即一次性处理（one-pass），或者再次提取数据的代价昂贵。如何对这些流数据进行存储、查询处理已经成为当前国际数据库研究领域的热点问题。在许多实际应用中，如决策支持系统、查询优化等，用户并不需要获得确切值，而只需要一个近似值。因此，数据流分析和管理的核心是设计一次扫描算法，即在一个远小于数据规模的内存空间里不断更新一个代表数据集的结构—概要数据结构，使得在任何时候都能够根据这个结构快速实时地获得近似查询结果。如果流的长度为N，则概要数据结构的规模大小不超过0（polylog（N）），并且处理流上每一组数据的时间不超过0（polylog（N））。传统数据库中的查询主要是一次查询，即系统根据当前数据集合的快照给出查询结果，并将该结果返回给用户。而数据流的查询为连续查询，即查询随着新数据的到来而不断的返回查询结果。连续查询是数据流上特有的操作，具有长期运行的特点。由于数据流环境中的数据集不是静态的，而是不断有数据插入和更新。用户需要的也不是在某个时刻的静态查询结果，而是对整个数据流的一个动态监测，随着数据流的不断变化持续地产生查询结果。现有的数据流的研究主要为集中式的流数据系统，而数据流的本质是分布式的，越来越多如传感器网络、数据通讯、Internet流量分析和Web日志等的大量数据都来自不同的远程数据源，因此，需要构建分布式数据流查询处理的中间件以支持上述各种应用。P2P技术利用互联网的终端机来建立一个庞大的分布式计算网络，并对迅速涌出的大量信息进行处理。这些计算机（即对等点）在网络中处于同等的地位，各自拥有独立的网络自主权，以解决把所有的计算压力全部加在服务器一端所造成的瓶颈问题。P2P以其可扩展性、通信负载平衡，资源的高利用率以及由基于内容的路由机制所提供的动态变化的适应性等特性成为构建中间件的良好平台，以便在减少网络带宽和网络连接所消耗的计算资源情况下，提供快速有效的数据流查询处理的实时响应。本论文以分布式数据流为主要研究对象，分析了国内外的研究现状，从目前存在的问题和不足出发，研究数据流基于时间变化的特性，监测当前流入的数据，探索数据流变化的表示与建模方法，分析数据进化和变化的趋势，并对未来流入的数据进行预测。在大规模分布式环境中，研究时间和空间复杂度最小的分布式数据流查询处理和挖掘算法。一方面，研究小波分解技术，利用小波系数的近似处理方法构建和维护小波直方图，以获得好的精确度，并且将其扩展到多维直方图的构建和维护，解决传统的直方图技术难以解决的问题，并利用小波系数构造数据流集的概要，建立一个复合索引结构来响应各种查询；还研究小波多分辨分析思想，构造一种小波神经网络模型，解决了传统神经网络中隐层节点数难以确定的问题，初步建立分布式时间序列数据流的预测模型。另一方面，运用草图技术解决在数据流上的聚集查询等难点问题。研究分布式数据流中频繁项的发现算法，通过设置精确梯度来减少通信开销，实现数据流查询的实时响应。同时，以P2P环境的Chord网络结构和协议为平台，研究分布式数据流挖掘和及时响应查询处理的中间件，探索在对等计算系统中提供流数据的近似查询功能所涉及到的数据和查询路由、定位与查找、索引及数据流概要的映射等关键技术问题。具体来说，本论文的主要创新点在于以下四个方面：（1）研究了基于小波技术的分布式数据流的查询处理算法。首先通过离散小波变换理论与DWT分解哈尔小波方法获得小波系数，然后分析了数据流的计算模型，形式化了数据流的查询模型。在此基础上，提出了一种新的方法来构造数据流集的概要，建立一种复合索引结构来处理内积查询和相似查询。此外，还结合小波神经网络WNN良好的时频局部化性质以及神经网络的自学习功能，初步建立适应于时间序列数据流的预测模型。（2）研究了基于草图技术的分布式数据流的聚集查询算法。首先分析了基于草图的近似处理算法，然后利用随机技术，在数据流到达时实时计算数据的伪草图概要。在此基础上，提出新颖的草图分割技术，通过属性值域的智能分割来减小分割后的自联接规模以及为每个分割的独立草图公平地分配存储空间两个方面来保证近似估算质量。（3）研究了大规模分布式数据流中频繁项的发现算法。通过对单个数据流频繁项的发现算法的分析，形式化地定义了基于时间点的分布式数据流频繁项的发现问题。并提出了基于Lossy Counting算法的、分布式的合并算法DMA（Distributed Merging Algorithm）的一种分层结构来发现从叶子结点直至根结点的概要结构，并通过设置精确梯度使网络数量最小及数据中心和网络链接所消耗的计算资源最小来优化分布式系统的通信负载。（4）研究了基于P2P的分布式数据流查询处理的中间件和原型开发。首先利用P2P的特性改进了索引结构的定位查询过程和稳定性。然后，将数据流的概要映射到改进的弦环节点，将基于内容的路由扩展到分布式流索引中，在此基础上，提供连续近似查询，并利用最小边界矩形MBR等优化方法，通过自适应地调整MBR的每一维f的高低边界来改进系统的精确度。在减小中心数据和网络链接所消耗的计算资源的情况下，加快和提高流数据查询和挖掘的效率，及时响应客户的查询请求。本论文的研究依托于国家863项目“基于Web服务的数据库新技术”的子项目“基于Web服务的电子商务”的研究来进行。所有的科研工作是建立在对大量参考文献的阅读理解、理论分析和实验测试的基础上，经实验和分析表明，所提出的算法和基于P2P的中间件具有良好的性能特性，可以为分布式数据流应用提供运行与开发的环境。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 引言
• 1.2 数据流查询处理技术的研究
• 1.2.1 数据流的基本概念
• 1.2.2 当前的研究现状
• 1.2.3 数据流模型
• 1.2.4 数据流算法
• 1.2.5 查询语义
• 1.2.6 数据流查询处理存在的问题
• 1.3 数据流环境下的挖掘技术
• 1.3.1 数据流挖掘的相关工作
• 1.3.2 数据流聚类的挖掘算法
• 1.3.3 数据流频繁模式的挖掘算法
• 1.3.4 数据流分类挖掘算法
• 1.3.5 数据流挖掘存在的问题
• 1.4 Peer-to-Peer技术
• 1.4.1 Peer-to-Peer的定义
• 1.4.2 P2P网络与现有互联网技术比较
• 1.4.3 P2P技术的应用
• 1.4.4 P2P系统需要解决的问题
• 1.5 课题意义及本文的研究内容
• 1.5.1 课题来源
• 1.5.2 研究内容
• 1.5.3 论文的组织结构
• 第2章 基于小波变换的分布式数据流的查询处理
• 2.1 引言
• 2.2 基于小波的近似处理技术
• 2.2.1 小波系数的分解
• 2.2.2 基于小波直方图的构建
• 2.2.3 基于小波直方图的动态维护
• 2.2.4 实验估算
• 2.3 基于小波近似技术的数据流的查询处理
• 2.3.1 相关工作
• 2.3.2 数据流和查询模型
• 2.3.3 系统结构和解决方案
• 2.3.4 性能评估
• 2.4 基于小波神经网络的数据流挖掘研究初探
• 2.4.1 多分辨率分析理论
• 2.4.2 预测的基本问题
• 2.4.3 小波神经网络模型
• 2.4.4 小波神经网络的学习算法
• 2.4.5 实验测试
• 2.5 结论
• 第3章 基于草图的分布式数据流聚集查询的研究
• 3.1 引言
• 3.2 分布式数据流处理模型
• 3.3 伪随机草图概要
• 3.4 基于草图技术的近似查询应答
• 3.4.1 基于草图技术的 COUNT查询应答
• 3.4.2 基于草图技术的 SUM查询应答
• 3.5 草图分割算法
• 3.5.1 基本定义
• 3.5.2 草图分割算法
• 3.6 实验
• 3.7 结论
• 第4章 分布式数据流频繁项发现算法的研究
• 4.1 引言
• 4.2 单个数据流频繁项的发现算法
• 4.3 分布式数据流频繁项的发现算法
• 4.3.1 问题的形式化定义
• 4.3.2 现有算法存在的问题
• 4.3.3 分布式数据流频繁项的发现算法 DMA
• 4.4 精确梯度的设置与优化
• 4.4.1 根结点总负载的最小化
• 4.4.2 任意连接的最差情况负载的最小化
• 4.4.3 非最差情况输入的最小化
• 4.5 实验估算
• 4.6 结论
• 第5章 分布式数据流查询处理的 P2P中间件研究
• 5.1 引言
• 5.2 Chord网络
• 5.2.1 Chord网络构造方法
• 5.2.2 路由算法和特性
• 5.3 Chord协议和改进算法
• 5.3.1 一致哈希
• 5.3.2 简单的对象查询
• 5.3.3 改进的弦协议算法
• 5.3.4 稳定状态分析
• 5.3.5 失效与容错性
• 5.3.6 节点的离去
• 5.4 数据流查询和计算模型
• 5.4.1 流查询模型
• 5.4.2 流计算模型
• 5.5 系统结构和解决方案
• 5.5.1 系统结构
• 5.5.2 流概要到弦环节点的映射
• 5.5.3 基于内容的路由到分布式流索引的扩展
• 5.5.4 内积查询的处理
• 5.5.5 相似查询的处理
• 5.5.6 通信开销
• 5.6 性能估算实验
• 5.7 结论
• 第6章 总结与展望
• 6.1 研究工作总结
• 6.2 对未来工作的展望
• 附录
• 主要参考文献
• 读博期间发表和录用的论文
• 读博期间所参加的科研项目
• 致谢