《分布式数据流查询处理若干关键技术的研究》由会员分享，可在线阅读，更多相关《分布式数据流查询处理若干关键技术的研究（144页珍藏版）》请在金锄头文库上搜索。
1、东华大学博士学位论文分布式数据流查询处理若干关键技术的研究姓名：杨颖申请学位级别：博士专业：控制理论与控制工程指导教师：乐嘉锦20060601析和W e b 日志等的大量数据都来自不同的远程数据源，因此，需要构建分布式数据流查询处理的中间件以支持上述各种应用。P 2 P 技术利用互联网的终端机来建立一个庞大的分布式计算网络，并对迅速涌出的大量信息进行处理。这些计算机( 即对等点) 在网络中处于同等的地位，各自拥有独立的网络自主权，以解决把所有的计算压力全部加在服务器一端所造成的瓶颈问题。P 2 P 以其可扩展性、通信负载平衡，资源的高利用率以及由基于内容的路由机制所提供的动态变化的适应性等特性
2、成为构建中间件的良好平台，以便在减少网络带宽和网络连接所消耗的计算资源情况下，提供快速有效的数据流查询处理的实时响应。本论文以分布式数据流为主要研究对象，分析了国内外的研究现状，从目前存在的问题和不足出发，研究数据流基于时间变化的特性，监测当前流入的数据，探索数据流变化的表示与建模方法，分析数据进化和变化的趋势，并对未来流入的数据进行预测。在大规模分布式环境中，研究时间和空间复杂度最小的分布式数据流查询处理和挖掘算法。一方面，研究小波分解技术，利用小波系数的近似处理方法构建和维护小波直方图，以获得好的精确度，并且将其扩展到多维直方图的构建和维护，解决传统的直方图技术难以解决的问题，并利用小波系
3、数构造数据流集的概要，建立一个复合索引结构来响应各种查询；还研究小波多分辨分析思想，构造一种小波神经网络模型，解决了传统神经网络中隐层节点数难以确定的问题，初步建立分布式时间序列数据流的预测模型。另一方面，运用草图技术解决在数据流上的聚集查询等难点问题。研究分布式数据流中频繁项的发现算法，通过设置精确梯度来减少通信开销，实现数据流查询的实时响应。同时，以P 2 P环境的C h o r d 网络结构和协议为平台，研究分布式数据流挖掘和及时响应查询处理的中间件，探索在对等计算系统中提供流数据的近似查询功能所涉及到的数据和查询路由、定位与查找、索引及数据流概要的映射等关键技术问题。具体来说，本论文的
4、主要创新点在于以下四n个方面：( 1 ) 研究了基于小波技术的分布式数据流的查询处理算法。首先通过离散小波变换理论与D W T 分解哈尔小波方法获得小波系数，然后分析了数据流的计算模型，形式化了数据流的查询模型。在此基础上，提出了一种新的方法来构造数据流集的概要，建立一种复合索引结构来处理内积查询和相似查询。此外，还结合小波神经网络W N N 良好的时频局部化性质以及神经网络的自学习功能，初步建立适应于时间序列数据流的预测模型。( 2 ) 研究了基于草图技术的分布式数据流的聚集查询算法。首先分析了基于草图的近似处理算法，然后利用随机技术，在数据流到达时实时计算数据的伪草图概要。在此基础上，提出
5、新颖的草图分割技术，通过属性值域的智能分割来减小分割后的自联接规模以及为每个分割的独立草图公平地分配存储空间两个方面来保证近似估算质量。( 3 ) 研究了大规模分布式数据流中频繁项的发现算法。通过对单个数据流频繁项的发现算法的分析，形式化地定义了基于时间点的分布式数据流频繁项的发现问题。并提出了基于L o s s yC o u n t in g 算法的、分布式的合并算法D M A ( D i s t r i b u t e dM e r g i n gA l g o r i t h m ) 的一种分层结构来发现从叶子结点直至根结点的概要结构，并通过设置精确梯度使网络数量最小及数据中心和网络链接
6、所消耗的计算资源晟小来优化分布式系统的通信负载。( 4 ) 研究了基于P 2 P 的分布式数据流查询处理的中间件和原型开发。首先利用P 2 P 的特性改进了索引结构的定位查询过程和稳定性。然后，将数据流的概要映射到改进的弦环节点，将基于内容的路由扩展到分布式流索引中，在此基础上，提供连续近似查询，并利用最小边界矩形M B R 等优化方法，通过自适应地调整M B R 的每一维f 的高低边界来改进系统的精确度。在减小中心数据和网络链接所消耗的计算资源的情况下，加快和提高流数据查询和挖掘的效率，及时响应客户的查询请求。本论文的研究依托于国家8 6 3 项目“基于W e b 服务的数据库新技l l I
7、术的子项目“基于W e b 服务的电子商务“ 的研究来进行。所有的科研工作是建立在对大量参考文献的阅读理解、理论分析和实验测试的基础上，经实验和分析表明，所提出的算法和基于P 2 P 的中间件具有良好的性能特性，可以为分布式数据流应用提供运行与开发的环境。I V关键词：分布式数据流，概要数据结构，离散小波变换，语义查询，一致哈希，中间件R e s e a r c ho nS o m eK e yT e c h n i q u e so fD i s t r i b u t e dD a t aS t r e a mf o rQ u e r yP r o c e s s i n gA b s t
8、 r a c tW i t ht h ed e v e l o p m e n to fl a r g en e t w o r ka n dW e ba p p l i c a t i o n ，an e wk i n do fd a t a- D a t as t r e a mc o m ei n t ob e i n gi nt h ea p p l i c a t i o na r e a so fm o n i t o ra n ds e n s o rn e t w o r k 、i n - b r e a kd e t e c t i n g 、c o m m u n i c
9、a t i o nd a t am a n a g e m e n t 、s t o c ka n a l y s i sa n dS Oo n T h e s ed a t as e q u e n c ea r er e l a t i o n a lt u p l e s 、s e n s o rv a l u e s 、n e t w o r kp a r a m e t e r s 、p h o n er e c o r d sa n ds h a r ed a t ae t c D i f f e r e n tf r o mt r a d i t i o n a ld a t a
10、 b a s ea p p l i c a t i o nm o d e l ，d a t as t r e a mm o d e lh a v ec h a r a c t e r i s t i c sa sb e l o w ：( 1 )C o n t i n u o u s ，r e a lt i m ea r r i v a l ：( 2 ) V a s t ，u n r e s t r a i n t e da n dh a r de s t i m a t e d ：( 3 )U n l e s ss t o r i n ge s p e c i a l l y ，t h e y
11、c a n tb et a k e no u tt oh a n d l ea g a i n ，n a m e l yo n e p a s sp r o c e s s i n g O t h e r w i s e ，w i t h d r a w i n gd a t aa g a i ni sv e r ye x p e n s i v e H o wt os t o r e 、q u e r ya n dm i n et h e s ed a t as t r e a n sh a sb e c o m et h eh o ti s s u e si nt h ef i e l d
12、o fi n t e r n a t i o n a ld a t a b a s ec u r r e n t l y I nm a n yp r a c t i c a la p p l i c a t i o n ，s u c ha sd e c i s i o ns u p p o r ts y s t e m 、q u e r yo p t i m i z a t i o n ，t h ee x a c tv a l u e sa r en o tn e c e s s a r yt Oo b t a i nb u ta p p r o x i m a t ev a l u e T
13、h e r e f o r e ，t h ec o r ei s s u eo fd a t as t r e a mm a n a g e m e n ta n da n a l y s i si sd e s i g n i n go n e - p a s sa l g o r i t h m ，n a m e l yt h ef e a t u r es t r u c t u r eo fd a t as t r e a m - -s y n o p s i sd a t as t r u c t u r ea r eu n c e a s i n g l yu p d a t e
14、di nt h el e a s tm e m o r yt h a nd a t as c a l ei no r d e rt Oq u i c k l ya c h i e v ea p p r o x i m a t i o na n s w e ri nt i m ea ta l lh o u r s I ft h el e n g t ho fd a t as t r e a mi sN ，t h es i z eo fs y n o p s i ss t r u c t u r ea r en o te x c e s st oO ( p o l y l o g ( N ) )
15、，a n dt h ep r o c e s s i n gt i m eo fe a c hg r o u po fs t r e a ma r en o te x c e s st oO ( p o l y l o g ( N ) ) T h ep r i m a r yq u e r yi nt r a d i t i o n a ld a t a b a s ei so n e t i m eq u e r i e s ，n a m e l yt h es y s t e mg i v ea n s w e ra c c o r d i n gt Ot h es n a p s h o
16、 to fd a t a s e t B u ti nd a t as t r e a m s ，t h eq u e r yi sc o n t i n u o u sa n dl o n g r u nb e c a u s et h eq u e r ya n s w e r sa r er e t u r n e di n c e s s a n t l ya l o n gw i t hn e wd a t a T h ed a t as t r e a m sa r en o ts t a t i cb u tc e a s e l e s si n s e r t i o na n du p d a t e U s e r sn e e dd y n a m i cm o n i t o r i n ga l o n gw i t ht h ec h a n g e dd a t as t r e a m sb u tn o ts t a t i cr e s u l to fs o m et i m e T h ee x i s
