（计算机科学与技术专业论文）数据流上复杂序查询的研究与实现.pdf

浙江大学硕士学位论文摘要 摘要 所谓数据流，就是指大量连续产生，持续到达，并且潜在无限的数据序列。 在网络监控、金融服务、w e b 页面访问、股票市场、以及传感器网络中，数据均 以流的形式出现，满足了数据流的定义。由于数据流数据的特殊性，其海量数据 很难被完全归档，因此针对于数据流的处理，往往需要在一次或者是有限次的顺 序读取中获取最终的结果。传统的基于归档数据而研发出来的算法，例如聚类算 法k m e a n s ，k c e n t e r s ，频繁项挖掘算法a p r i o r i ，f p - t r e e ，当应用在数据流环境 中时，都遇到了或大或小的问题，需要被修改甚至是完全重新设计才能满足新的 需求。而本文关注的正是数据流研究领域一个热门话题：数据流上的序查询。本 文围绕着数据流上的序查询展开讨论，首先( 第一章) 给出了数据流上的序查询 的定义及其应用，并分析了现有序查询研究在处理复杂问题上的不足之处。其次 ( 第二章) 对目前世界上此研究领域的研究现状进行了分析，并对其中两种较为成 熟的算法做了详尽的介绍。在此基础上，本文的第三部分( 第三、四章) 重点提 出了基于多维数据流上的一种新型的复杂序查询基于聚类的序查询，以及相 应的解决方案多层次块状结构处理算法，详尽的理论分析与实验，则展现了 该算法不仅具有可控的空间复杂度，同时也具备较优的查询性能。本文的最后部 分( 第五章) ，对数据流上复杂的序查询研究做了总结，并且给出了此研究领域目 前仍旧存在的问题，以及后续可以持续开展的研究热点。 关键词：数据流，多维数据流，序查询，分位数，聚类，近似查询，滑动窗口 a b s t r a c t d a t as t r e 锄sd i f f e rf r o mc o n v e n t i o n a ls t o r e dd a t ai nt h r e em a i nc h a r a c t e n s t l c s ， w h i c ha r ec o n t i n u o u s l yp r o d u c i n g ，o n l i n ea r r i v i n g ，a n dp o t e n t i a l l yu n b o u n d e d i ns l z e d a t as 仃e 帅se m e r g ei nm a n ya p p l i c a t i o n s ，j u s t l i k en e t w o r km o n i t o r i n g ，t l n 绷c l a l s e n ，i c e s w e bs i t cv i s i t i n g ，s t o c km a r k e t i n g ，a n d s e n s o rn e t w o r km o n i t o r i n g u a t a s 臼e a m sc a n n o tb ee a s i l ya r c h i v e df o ri t s u n b o u n d e di ns i z e ，s ow eo n l yh a v et h e c h a n c et 0r e a dt h ed a t aw er e c e i v e ds e v e r a lt i m e so re v e no n c eb e f o r ew er e p o r t t h e q u e r yr e s u i t s c o n v e n t i o n a la l g o r i t h m sd e v e l o p e df o r a r c h i v e dd a t a ，l i k ek - m e 锄s ， k c e n t e r sf o rd a t ac l u s t e r i n g ，a p r i o r i ，f p - t r e ea l g o r i t h m s d e v e l o p e df o rf r e q u e n t p 砒e mm i n i n g ，c a n n o tb eu s e di nd a t as t r e a me n v i r o n m e n t s w i t h o u tm o d i t i i c a t l o n i n “sd i s s e 眦i o n ，w ef o c u so no n e h o tr e s e a r c ht o p i ci nd a t as t r e a m s ，w h i c hl sk n o w n a s r 粕kq u e r y f i r s t ( c h a p t e r1 ) ，w eg i v et h ed e f i n i t i o no fr a n kq u e r yo v e rd a 诅妣锄s a n dd e s c r i b es o m ea p p l i c a t i o nc o n t e x t s ，t o g e t h e rw i t hd i s a d v a n t a g e sa m o n g a l lt h e p r e v i o u sr e s e a r c h e s s e c o n d ( c h a p t e r2 ) ，w eg i v e a l lo v e r v i e wo ft h ec u l t e n ts l t u a t l o n o ft h i sr e s e a r c ha r e a e s p e c i a l l y , t w of o r m e ra l g o r i t h m sw h i c hp r o v e d t ob em a t u r ea r e d i s c u s s e dd e t a i l e dh e r e t h i r d ( c h a p t e r3 、4 ) ，w ep r o p o s ea m u c hm o r ec o m p i e xr a n k q u e r yo v e rm u l t i d i m e n s i o n a ld a t as t r e a m s w e n a m et h i sc o m p l e xr a n kq u e r y 嬲 d 淞御6 鲫鲥m 七q u e r y f o rt h i sn e wr a n kq u e r y , w ep r o p o s ean o v e ia l g o r i t h m w h i c ha d o p t sam u l t i 1 e v e lb u c k e t s f r a m e w o r k t h e o r e t i c a la n a l y s i sr e v e a l s t h a tt h e a l g o r i t h mh a saw o r s t - c a s es p a c er e q u i r e m e n t t h ee x t e n s i v ee x p e r i m e n t sm d l c a t e t h a t t h ep r o p o s e da p p r o a c hi se f f i c i e n ti nb o t ht i m ea n ds p a c e w h e np e 渤n n i n gd a t as t r e 踟 p r o c e s s i n ga n dc l u s t e r - b a s e dr a n kq u e r y , a n d c a na l s oa c h i e v eg o o dc l u s t e r i n gq u a l i t y a n dg u a r a n t e e de r r o rp r e c i s i o n i nt h el a s tp a r to ft h i s d i s s e r t a t i o n ( c h a p i t e r5 ) ，w eg a v e ac o n c i u s i o na sw e l la sf u t u r ed i r e c t i o n si nt h i sr e s e a r c ha r e a k e y w 。r d s ：d a t a s t r e a m ，m u i t i d i m e n s i o n a ld a t as t r e a m ，r a n kq u c r y ，q u a n t i l c ， c l u s t e r i n g ，a p p r o x i m a t eq u e r y , s li d i n gw i n d o w i i 浙江大学硕士学位论文 图目录 图目录 图2 1 拥有1 6 项数据的数据流1 9 图3 1c l u s t r e a m 算法所维护之数据结构。31 图3 2c l u g k 算法流程图3 2 图3 3 多层次块结构处理算法数据模型图。4 0 实验4 1 聚类质量实验5 6 实验4 2 在线维护过程的执行效率比较5 8 实验4 3 在线维护过程的空间效率比较5 9 实验4 - 4 序查询过程的执行效率比较6 0 i i i 浙江大学硕士学位论文表日录 表目录 表2 1 序查询符号名及其意义1 4 表3 1 本文所涉及数据符号及其意义。2 8 表3 - 2 多层次块状结构处理算法全局参数。4 6 表4 1 对比实验的参数配置5 4 浙江大学硕士学化论文第1 章绪论 第1 章绪论 本章将介绍数据流以及数据流上的序查询的基本概念。首先是数据流的基本 概念，包括数据流的产生，数据流的特性，数据流模型和数据流上的主要研究工 作。其次是数据流上的序查询介绍，涉及到数据流上序查询的定义，应用场景以 及当前研究存在的不足之处。在本章的最后，我们将给出此论文研究的意义所在。 1 1 数据流概述 1 1 1 数据流的产生 近年来，随着科技水平的不断进步，数据密集型应用纷纷产生，传统关系型 数据库系统受重视程度日益提高，在金融领域、互联网领域、军事领域等都得到 了极大地应用。但是，在所有这些数据密集型应用中，有一类新的应用，由于其 特殊性，却很难用传统的数据库系统进行存储，查询工作。这类新的应用中数据 的共同特点是：大量产生，连续到达，数据量潜在无限。事先很难预知数据达到 速度以及总数据量。目前，研究界给此类数据起了个形象的名字数据流( d a t a s t r e a m ) ，针对此类数据的研究都被归结于数据流领域的研究。 数据流应用产生于多个领域。最早的包括银行和股票交易领域，银行交易及 股票价格走势数据，都满足数据流数据的特征。对股票价格数据的分析，能够帮 助我们挖掘关联股票，识别股票走势，甚至是预测股票未来价格等等。当然，此 类应用也可以通过将数据存储在后台数据库管理系统中，然后通过调用传统的基 于归档数据的挖掘算法得来，但是，在瞬息万变的股票市场，离线的处理由于其 过高的延时性而使得其重要性大打折扣。而基于在线的数据流处理，能够很好的 弥补传统数据库方法的缺陷，给用户以更好的实时性指导。近年来，随着传感器 技术的发展，传感器网络构成了数据流的另一个应用领域。传感器网络可以部署 在不同的监控应用之中，其产生的数据正符合数据流数据的种种特征。例如，我 浙江大学硕士学 t 论文第1 章绪论 们可以部署传感器于城市煤气管道之中，实时采集数据，用于监控煤气泄漏：或 者，将传感器部署于机动车辆的关键部位，用于实时监控当前机动车辆的健康信 息，等等。针对于此类数据的查询与挖掘，对实时性的需求较高，煤气泄漏最好 能在发生时就报警，检测到的车辆上的各种不良信息，第一时间报警维修则能很 好的消除车祸隐患。在这些应用中，传统数据库系统也显示了其不足之处，我们 需要为数据流应用提供更有针对性的解决方案。除此之外，数据流应用还产生与 生活中的其余各个方面，包括移动互联网络，事务日志分析等。 1 1 2 数据流的特性 国内外对数据流数据的研究，在上世纪9 0 年代末开始出现，而在本世纪发 展壮大。在一篇数据流研究综述性文章中【1 1 ，b a b c o c k 等人对数据流与传统关系 型数据做了完整对照比较之后，提出了一下四点不同之处： 数据流中的数据项是在线连续达到的。 系统无法控制数据流数据的达到顺序，无论是对单个数据流，还是处理 多数据流。 数据流中的数据量是潜在无限的。 系统每处理完一条数据流中的数据项，此数据项要么被丢弃，要么被归 档。但无论是那种情况，再次访问该数据项都不是一件很容易的事。快 速访问归档数据需要保证此数据在内存之中，但是考虑到数据流的无限 性，内存空间往往是不足的。 数据流的种种特性，决定了数据流处理，相对于传统数据处理，有其不同之 处： 在线处理，持续处理。数据流中的数据持续到达，决定了数据流处理必 须满足在线实时处理的要求。同时，数据持续更新，处理的结果也就需 要实时更新。如果我们将传统关系型数据库处理系统看作是数据不变， 查询变化的模型；那么数据流处理则更像是一种查询不变，而数据实时 2 浙江大学硕士学f t 论文第1 章绪论 变化的模型。 有限存储，一次扫描。数据流数据的潜在无限性，从根本上杜绝了存储 所有数据的可能性。无论是公司，研究机构，还是个人，都很难有无限 的空间来满足存储的要求。因此，这也对数据流数据的访问提出了要求， 系统必须在仅仅对数据进行一次扫描读取的过程中，收集信息，并得出 最终的处理结果。 快速响应。数据流应用的特点，例如股票交易应用，或者是传感器网络 应用，都对处理的实时性提出了苛刻的要求。更早的处理结果返回，要 么对用户提供更好的指导，要么能将灾难扼杀于无形。 近似结果。如果说传统的关系型数据库管理系统必然返回精确结果，那 么数据流处理就允许近似结果的出现。造成这个的出现，有两方面的原 因，一是在不存储所有数据，一次扫描的限制下，系统得不到精确的结 果；二是为了满足高实时性的要求，近似结果能够快速计算得出，但是 精确结果却需要花费大量时间，在保证实时性之下，用户允许近似结果 的出现。 1 1 3 数据流的主要模型 近年来，随着数据流研究的升温，研究人员提出了各种各样的数据流模型， 由于本文并不是关注于模型研究，因此我们并没有包括所有这些模型，只是将其 中比较重要的和常见的加以介绍，并选取其中的一种作为本文使用的模型。假设 数据流( 用d 表示) ，是由一系列数据项( 用x 表示) 构成，d = 五，砭，鼍，) ， 那么不同数据流模型之间的区别，主要在于数据项x 的不同： 基本模型。数据流基本模型是最基础的数据流模型，其数据项定义如下： x = ( v ) ，v 代表了该数据项的取值，可以是一维数据，也可以由多维数 据构成。 时间戳模型。数据流时间戳模型，通过在基本模型内添加了时间戳信息， 浙江大学硕士学位论文 第l 章绪沦 使得单一数据项记录的信息更为丰富，形如：x = ( v ，) ，v 为数据项取 值，则表示此数据项产生的时间。在实际应用中，无论是传感器网络， 还是股票市场数据，都会产生带时间戳的数据，因此，数据流时间戳模 型也是研究中使用最广的模型。 更新模型。数据流更新模型，相对于前面的模型更为复杂，其表现形式 为：x = ( v ，t ，c ) ，v 是取值，t 是时间戳，而c 则表示了此数据项的更新 动作。c + ，一) ，+ 表示此数据项为插入的新数据，而一则表示此数据项 是用来删除前面出现的数据。数据流更新模型，使得数据不仅可以插入， 而且已经到来的数据还可以删除。此模型的优点在于其容错能力强大， 前面产生的错误数据，可以通过后序的观察消除。但是此模型缺点也很 突出，一是过于复杂，二是由于数据流一次扫描，数据不归档的特性， 导致此模型实际价值不大。 在本文中，我们选用数据流时间戳模型作为基准模型。在文章的余下部分， 只要提到数据流，都是指时间戳模型的数据流。 1 1 。4 数据流关键技术研究 数据流是一个重要的研究领域，包括了大量的研究分支，从功能上来说，主 要可以划分为以下几个部分： 1 数据流基本问题处理。基于数据流数据的基本问题处理，涵盖了以下一 些问题点：数据流上的序查询研究【2 3 4 】；数据流上最大值、最小值、中间值 查询【5 q ；数据流上的频繁项查询，范围查询【7 8 9 。 2 数据流数据挖掘。传统的数据挖掘算法，在数据流环境下，都遇到了不 小的问题，因此，这也使得一系列符合数据流特性的挖掘算法应运而生。包 括数据流上的聚类研究【1 】；数据流上的频繁集挖掘【1 2 1 31 4 】；数据流上的模式 匹配、子序列检测【1 5 1 61 7 j ；数据流上的复杂事件处理【1 81 9 2 0 2 1 捌；数据流上的 最长递增( 递减) 子序列查找 2 32 4 1 等等。 4 浙江大学硕士学位论文第1 章绪论 3 数据流系统级实现。数据流领域一个重要的研究工作，就是制定一整套 符合数据流特性的并且区别于传统关系型数据库管理系统的数据流管理系统 ( d a t as t r e a mm a n a g e m e n ts y s t e m ) ，这也是数据流研究的初衷及关键所在。 数据流管理系统的原型系统最初诞生于国外知名大学的实验室之中。这其中 的翘楚包括s t a n f o r d 大学的s t a n f o r ds t r e a md a t am a n a g e r ( s t r e a m ) 1 2 5 1 ， b e r k e l e y 大学的t e l e g r a p h c q 系统 2 6 1 ，以及b r o w nu n i v e r s i t y 与m 1 t 联合开 发的a u r o r a 系统【2 7 】等。这些原型系统或者相对简单( s t r e a m ) ，或者改版 于传统数据库系统( t e l e g r a p h c q ) ，但是他们都实现了数据流管理的相应功 能，为以后的发展指明了道路。在这些原型系统之上，一批成熟的商业系统 出现在市场上，比较著名的包括s t r e a m b a s e 公司的s t r e a m b a s e 系统，该系统 是数据库专家m i c h a e ls t o n e b r a k e r 教授对数据流原型系统s t r e a m 的商业化 应用而产生的：除此之外，还有在近期合并的c o r a l 8 公司与a l e r i 公司的两 个同名产品，其中，c o r a l 8 系统也是在原型系统a u r o r a 的基础上发展而来的。 这些系统在业界的广泛使用，充分说明了数据流不仅仅属于大学实验室中的 研究，而且在商业中也具有相当高的价值。认识到这一点的传统数据库管理 系统提供厂商，也纷纷加入了这个领域。微软公司在他们最新发布的 s q l s e r v e r2 0 0 8r 2 中，就加入了数据流处理功能模块s 骶锄i n s i g h t 。而 作为数据库业界的大佬，o r a c l e 公司自然不甘人后，在数据库界知名的期刊 v l d b 上，o r a c l e 公司与s t r e a m b a s e 公司研究人员合作发表的论文【2 8 】，则 可以看作是o r a c l e 公司准备掌握数据流管理系统中查询语言标准制定的一个 强烈信号。 4 数据流不同数据类型处理。近年来，随着数据流研究的升温，国外的研 究人员又根据数据流中数据的不同类型进行细分，从而产生了基于不同数据 类型的数据流研究。这其中，最重要的两个研究方向，包括数据流领域的不 确定数据流研究【2 9 3 0 3 13 2 3 3 】，以及图数据流研究 3 4 3 5 】。 在所有的这些研究之中，数据流的序查询研究，伴随着数据流这一研究领域 的兴起，一直得到了世界各地研究人员的广泛关注。序查询研究应用广泛，可以 浙江大学硕士学位论文第l 章绪论 被用来回答数据流中诸如中位数查询，最大、最小值查询，以及数据分布情况查 询等等问题。数据流序查询的各种解决方案也是层出不穷，不同的算法从处理性 能，空间消耗，数据模型等不同角度出发，丰富了序查询的研究领域，扩大了序 查询的应用范围。在本文的以下部分，我们将逐步详细介绍数据流序查询研究的 定义，应用场景，国内外研究现状，乃至于提出自己的一种新型的多维数据流上 的复杂序查询问题多维数据流上基于聚类的序查询。 1 2 数据流序查询概述 在本节，我们主要讨论序查询的定义，数据流序查询的部分应用场景，以及 数据流上的序查询研究仍旧存在的不足之处。而数据流序查询的研究现状，将在 下一章中详细讨论。 1 2 1 数据流序查询定义 在数据流研究领域，其中一个重要的分支就是数据流上的序查询( r a n kq u e r y ) 研究，从本世纪初开始，国内外大量研究论文关注在这个点上，并且根据不同的 应用背景，提出了不同的解决方案。 一个完整的序查询定义【4 】如下：给定一个数据集d 与一个自然数r ，当然， 此数据集可以是存储于关系数据库中的一张表，也可以是通过传感器网络观测到 的数据流，对该数据集按照一个指定的排序函数进行排序然后返回排序完成后的 数据集中位于第r 位的数据项。 在实际应用过程中，序查询往往表现为另外一种形式，那就是分位数( q u a n t i l e ) 查询。同样，给定数据集d 与一个分位数矽，不同之处在于，序查询r 的取值范 围是自然数；但是分位数的取值范围却是( 0 ，1 1 ，0 到l 之间的一个小数。假定 数据集d 中有n 项数据项，对d 进行排序操作之后，分位数查询就是返回排 序完成之后的第- 项。也就是说，分位数查询就相当于序查询f | 矽a r 。 1 分位数就是数据集中的最大值，而o 5 分位数则是数据集中的中值，又称作中 6 浙江大学硕士学位论文第l 章绪论 位数。 例如，给定数据集d = 3 ，l ，4 ，2 ，9 ，6 ，8 ，7 ，5 ，1 0 ) 以及自然数r = 5 ， 将d 按照递增的顺序进行排序，得d = 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 ) ，那 么序查询r = 5 返回的查询结果就是数据集d 中的第五个数据项，“5 ) = 5 ( 排序从1 记起，而不是0 、。在同样的数据集上，也可以做分位数查询。例如，o 1 分位数 查询返回l ( r = f 矽n 1 = n ；0 5 分位数查询返回5 ，同r = 5 的查询结果；1 分位数 查询就是返回数据集中的最大值，在此处则返回10 。 序查询在传统的关系型数据库中根本不能称之为问题，因为数据库中保存了 所有数据，我们完全可以应用先排序，后查询的策略，返回完全精确的序查询结 果。但是，基于数据流的特性，这一策略在数据流环境下就不适用了。第一，为 了满足实时性的需求，数据流往往采用的是一次扫描的数据项访问方式，在此限 制下，目前的排序算法很难在一次扫描的过程中就完成所有的排序动作；第二， 由于数据流中的所有数据很难被完全归档存储，因此也造成了我们没法使用先排 序，后返回查询结果的原始策略。 由于在数据流环境下，序查询没法使用先排序，后查询的策略，同时，数据 流上的序查询还必须满足快速处理，一次扫描的需求，因此，国内外的研究人员 纷纷加入对于数据流序查询的研究之中，并且提出了大量不同的算法，来完成这 目标。虽然研究人员不同，提出的算法也不同，但是，大家却达成了一个共识： 在数据流环境下，完全精确的序查询是很难获得的，为了满足实时性，低存储消 耗的需求，返回序查询的近似结果是可以接受的方案。 1 2 2 数据流序查询应用场景 在现实生活中，数据流序查询拥有广泛的应用场景。包括w e b 序聚集查询与 日志挖掘【3 63 7 ，序查询能够发掘用户信息变化，指导网站的建设；传感器网络数 据分析【3 】，序查询能够分析传感器网络数据，挖掘隐藏在数据背后的信息；股票 市场趋势分析【13 8 】，序查询能够完成对股票价格分布及走势分析，指导用户更好 7 浙江大学硕士学位论文第l 苹绪论 的操作；以及分布式计算环境下的数据负载均衡分区 3 9 4 0 ，通过序查询分析数据， 能使研究人员更好的了解数据分布，设计出真正的负载均衡系统，等等。下面， 我们用一个应用实例，来说明数据流序查询在实际生活中所起的作用。 如今，世界的工业化进程不断加快，在提高人们生活水平的同时，也不可避 免的对环境造成了极大的破坏，其中，气候升温就是表现之一。目前正在召开的 丹麦哥本哈根国际气候大会，充分说明了全世界对于环境变化的重视。实时监控 世界各个地方的温度，湿度等走势，对我们研宄、了解地球的状况有很大的帮助。 而传感器网络的发展，使得这一目标成为了可能。通过部署传感器网络，能够定 时监控、采集、并且汇报数据信息。当然，数据的采集只是第一阶段的任务，通 过数据，提取其中的信息才是我们最终的目标。应用数据流序查询技术，研究人 员能够实时监控某一个传感器节点在最近一段时间之内的最高温度( 1 分位数) ， 中间温度( 0 5 分位数) ，甚至是整个数据流的温度分布情况( 通过采样不同分位数 下的温度值绘制而成1 。除此之外，研究人员还可以将当前拥有相同温度分布情况 的传感器节点归为一类，后序可以同时观察这些类似节点，如果其中一个节点的 温度分布相对于其余节点发生较大的偏差，那么就可以及时提取出这个情况，指 导研究人员去发掘产生此现象的背后原因所在。 总的来说，随着数据流数据的涌现，数据流序查询在现实生活中的各个方面 都能得到广泛的应用。我们不仅仅需要在提高算法的性能，降低算法空间复杂度 等方面下功夫，同时，针对实际应用，设计出更加有用的序查询，也是数据流序 查询研究领域的一个重点。 1 2 3 存在的问题 在分析了序查询的研究现状后，我们发现目前几乎所有的序查询研究所存在 的一个共性，那就是都是基于一维数据流，或者是多维数据流中的某一个维度。 但是，在调研了现阶段的基于数据流的部分应用之后，我们发现数据流数据往往 是多维甚至是高维的，不仅如此，此类应用对数据流序查询提出了更高的要求。 8 浙江大学硕士学位论文第1 章绪论 具体来说，用户对数据流聚类之后的序查询更感兴趣，查询每个聚类中的排序为 ，的数据项。可以考虑如下两个应用场景： 场景一。实时交通控制系统。目前，随着社会的发展，私家车越来越多，而 交通问题日益成为每个城市所需要面对的最大的问题之一。考虑一个城市的入城 公路监测点，每时每刻都有大量的车辆通过这个监测点，所有收集到的车辆信息， 就构成了一个数据流应用。当然，每个车辆信息都是多维数据，最主要的维度是 速度，其余的包括车辆的类型( 小车还是大车) ，车辆的牌照( 本地还是外地) ，车 辆的排量( 小排量还是大排量) 等等。 需要实时监控的是当前某一时间段内的车辆速度分布，发现速度分布不符合 平常状态，就需要通知管理人员检查原因所在。对于车辆的速度这一维度而言， 这是一个典型的数据流序查询应用。如果某一时刻，9 0 分位数的速度降低，则 说明整个监测点的流量降低了，某一时刻，9 5 分位数的速度明显增加，则说明 整个监测点有车速度加快了。此时，需要找来管理人员检查原因，但是，管理人 员会发现从仅仅基于速度这一个维度产生的序查询中，他得不到其他有用的信 息。 换个角度，考虑如果我们支持的是基于聚类的序查询，最终的结果就会好的 多。从每一个聚类中返回9 0 分位数的序查询结果，管理人员会发现，其实大部 分聚类中的结果并没有改变，仅仅只是小车聚类中的9 0 2 - ) 位数结果降低了，从 而说明是因为整个小车聚类的速度降低，而造成的整个监测点流量的下降。另外， 从每一个聚类中返回9 5 分位数的序查询结果，得出的问题则是，原有聚类中的 所有结果都不变，但是多了一个跑车的聚类，此聚类的9 5 分位数要远远大于其 余聚类中同分位数的速度。这一结果说明，在当前，有某个跑车车队在监测点以 高于其余车辆车速的速度行驶。管理人员从基于每个聚类返回的序查询结果中， 能够得到更多的信息，这些信息指导管理人员实时的作出决策，有时甚至都不需 要管理人员，系统就能做出决策，而这些在仅仅基于速度的全局序查询中，往往 是没办法得到的。 场景二。在线购物网站系统。考虑另外一个应用，一个在线购物网站，每一 9 浙江大学硕士学位论文 第l 章绪论 笔交易记录构成了一个数据流，如果此购物网站人流量很大，那么相应的每秒需 要处理的数据流数据也会很多。作为一个研究网上消费者的研究人员，或者是此 购物网站的维护人员，他可能对当前阶段一件热门商品的消费者年龄分布比较感 兴趣，当然，前提是消费者必须首先按照规则分为不同的种类。为了达到这一目 标，一个可行的方案就是，首先在线将目前阶段此商品的消费者按照其信息聚类， 然后针对于每一个不同的聚类，返回其中的基于消费者年来的序查询结果。 无论是场景一，还是场景二中的应用，都显示出了目前的基于一维数据的全 局序查询有其不足之处，有时候，我们需要一种更为复杂的序查询，来指导研究 人员管理人员研究问题，做出决策。而这一复杂的序查询，就是在多维数据流上 实现基于聚类的序查询。 1 3 本文研究内容和主要贡献 本文研究的重点就是数据流上的复杂序查询，具体来说，是多维数据流上基 于聚类的序查询。本文的研究意义及贡献如下： 本文对于数据流序查询的国内外研究现状，做了详尽的调研。 本文首先提出了一种新的序查询基于聚类的序查询，丰富了数据流 序查询领域的研究内容。 本文首次将数据流上的序查询研究与聚类研究结合起来。在此之前，数 据流上的研究人员，有的主攻基本查询，有的主攻数据流挖掘，但是两 类很少有交叉的成果产生，本文部分弥补了这一缺憾。 针对基于聚类的序查询这一新问题，本文提出了两种解决方案，一种融 合现有的算法，一种属于完全的原创算法。对于两种算法，本文都给出 了实现细节，而详尽的分析则展现了两种算法的优缺点。 在理论分析的基础之上，本文给出了详尽的实验结果。从各个方面对两 种算法进行比对。 + 本文分析了数据流序查询领域，数据流领域目前仍旧存在的研究问题， 1 0 浙江大学硕士学位论文第1 章绪论 以及未来可能的发展方向。 本文接下来的安排如下： 第二章，介绍数据流序查询的国内外研究现状，并重点分析两个已经被实践 证明是成功的算法。 第三章，首先给出了数据流上基于聚类的序查询这一新问题的完整定义。然 后，针对这一新的问题，提出了两种解决方案，分别是c l u g k 算法，以及多层次 块状结构处理算法，包括详尽的算法实现与理论分析。 第四章，我们从聚类质量，算法的空间复杂度，时间复杂度等各方面出发， 做了详尽的实验对比，从实验的角度再次验证两种算法。 第五章，我们对全文进行了总结，并对未来仍旧存在的研究问题，作了分析 与探讨。 1 4 本章小结 ， 本章重点讨论了数据流和数据流上序查询的基本概念。首先是数据流的基本 概念，包括数据流应用产生的原因，数据流区别于传统归档数据的特性，数据流 的主要数据模型，以及数据流领域的主要研究工作。然后，根据本论文的研究， 重点选取了数据流上的序查询做详细的介绍，从数据流序查询的定义出发，到数 据流序查询的应用场景，并且着重分析了当前数据流序查询技术在处理复杂问题 时所面临的不足之处。从中可以看出，数据流序查询定义清晰，应用广泛，而且 目前也存在着不足之处，值得进行深入的研究。在本章的最后部分，我们指出了 此论文研究的主要贡献及意义所在。 浙江大学硕士学位论文第2 章数据流序查询研究现状 第2 章数据流序查询研究现状 数据流上的序查询，有着清晰的问题定义，广阔的应用领域支持，从提出之 日起，就一直受到了国内外研究人员的广泛关注，产生了大量的研究成果。在本 章，我们将主要分析数据流上的序查询表现出来的特征，以及国内外在此领域的 相关研究。并重点分析其中的两个被证明为成功的算法：g k 算法f 2 】与g k 改进算 法【3 1 。同时，在完备的相关研究工作的支持之上，我们给出了本文的研究思路一 一提出一种在多维数据流上基于聚类的序查询。 2 1 数据流上序查询特性 数据流上的序查询，相对于传统关系型数据库中的排序操作，有相当多的不 同之处，除了前面提到过的返回近似结果之外，序查询在很多其他方面都展现出 了数据流的特性。总的来说，根据不同研究论文的着重点，数据流上的序查询， 展现出如下几个特性： 近似结果( 。由于数据流的特性，导致数据流上的序查询，往往很难返 回完全正确的结果。而几乎所有的研究，都采用了返回近似结果的方式， 来处理数据流上的序查询。同时，近似结果也分为两类，分别是一致性 近t 以( u n i f o r me r r o r ) ，以及相对性近似( r e l a t w ee r r o o 。给定当前拥有个 数据项的数据流d ，序查询，和错误率占，一致性近似返回结果，t 必须满 足：匕二型占，此时可以说，是，的一致性近似；而相对性近似的返回 r ”一ri 结果r 一则必须满足：匕占，此时可以说，一是r 的相对性近似。从 ， 条件中可以看出，相对性近似比一致性近似的错误率更低( ，n ) ，同时， ，越小，相对性近似返回的结果就更加贴近实际值，而这在部分数据流 应用中更加有效。 分位数形式( ) 。数据流上的序查询，一般都是以分位数形式，而不是原 始的给定序的形式，来查询结果。例如，给定当前拥有个数据项的数 1 2 浙江大学硕士学位论文第2 章数据流序查询研宄现状 据流d ，分位数妒( 一q u a n t i l e ) 和错误率，一致性近似被重定义为： 下i r - 矽n ll 占；相对性近似被重定义为：止苦鬟产占。相当于序查 询，= f c n l 。 空间消耗限制。数据流上的序查询，另一个关键特性是其必须保证空间 消耗在可控，可接受的范围之内。数据流是潜在无限的，但是我们却必 须保证我们的算法能够在有限的空间限制之内，实时的返回序查询的近 似结果。为了满足这一特性，现阶段提出的数据流序查询算法，都不会 保存所有原始数据，而是采用对原始数据采样【3 9 1 ，或者是保存原始数据 统计信息【2 】等技术，使得算法能在很小的空间消耗之内返回符合用户需 求的查询结果。 非精确的近似结果( 万，s ) 。为了保证数据流序查询算法的空间消耗限制， 部分研究人员提出了基于采样的技术。基于采样的技术，其优势在于处 理简单、快速，空间可控，但是，其缺点也是相当突出的，由于没有访 问所有的数据流数据项，因此也引入了更多的不确定性一一不仅返回结 果是近似的，而且就算是此近似结果的可靠性也是不确定的。给定数据 流d ，序查询，和错误率( 万，占) ，非精确的一致性近似定义如下： 尸( 匕笋占) l 一万( 匕笋占的概率要大于l 一万) 。相对于精确的一致 性近似，多了参数万，一般而言，万，占都是极小值，保证了结果的近似 性。 滑动窗口模型。基于数据流中的数据项持续产生，连续到达的特性，导 致在某些数据流实际应用环境下，新产生的数据项，往往比老的数据项 更有价值。例如，在在股票市场中，新数据对用户的指导意义更大；在 网络应用中，管理人员往往对用户在最近一段时间之内的数据更感兴趣。 这种对数据的偏爱程度，反应在研究领域，就产生了基于滑动窗口模型 的数据流研究技术。相对于传统的界标模型( l a n d m a r km o d e l ) ，滑动窗e l 浙江大学硕士学位论文第2 章数据流序查询研究现状 模型( s l i d i n gw i n d o wm o d e l ) 只关心数据流中的最新数据，而对于已经过 期的老数据，则不予处理。滑动窗口模型一般有两种：基于数据项数的 滑动窗口，只关心最近产生的项数据；以及基于时间的滑动窗口，只 关心最近f 时间段内的数据。 其他方面特性。除了前面归纳的特性之外，数据流上的序查询还需要处 理一些其余的问题点，这些问题点包括：处理分布式环境下的序查询【3 1 ； 针对拥有重复项数据的数据流序查询研列4 14 24 3 1 ；乱序到达数据流环境 下的序查询研列“4 5 】；基于不确定数据流上的序查询研究等等。 在本章的以下部分，我将从这些特性出发，简要介绍数据流上的序查询的研 究成果，并选取两种有代表性的研究算法，做详尽的分析介绍。然后，在此基础 上给出本文的研究思路。下面给出的符号表表2 1 ，说明了各符号在数据流 序查询中的意义。 表2 - 1 序查询符号名及其意义 符号名 符号意义 d数据流 n 数据流中的数据量 占 精度需求，( 1 一s ) 即为相似度 矽 分位数查询中的分位数值，矽【0 ，1 】 万 非精确的相似查询中的非精确度 r 给定序查询值，0 ，n ，竹 返回的序查询结果 u 数据流中的数据取值值域 2 2 数据流序查询研究现状分析 数据流上的序查询研究，从上世纪末开始，到目前仍旧是数据流研究领域的 热点之一。在这期间，国内外大量研究人员针对数据流序查询研究的不同特性， 提出了大量原创的算法。 m a n k u ，r a j a g o p a l a n ，与l i n d s a y 在论文【4 6 】中，提出了一种基于一次扫描基 1 4 浙江大学硕士学位论文第2 章数据流序查询研究现状 础上的序查询算法。该算法的空间复杂度为o ( - jl 0 9 2 ( 州) ) ，返回确定的一致性近 5 似结果( 1r t - r 匿g ) 。但是，此算法也有相应的不足，必须事先知道数据流中确 切的数据项数目，在数据流环境下，数据项连续达到，数据项数实时更新，因 此我们很难知道数据流中到底有多少数据。在论文【2 】中，研究人员g r e e n w a | d 与 k h a n n a 提出了另一种序查询算法。该算法不仅将 4 6 d p 的空间复杂度降低到了 o ( l l o g ( o n ) ) ，同时此算法也去除了必须事先知道数据项数的限制。此算法的 s 优势在于，操作简单，易于理解，空间复杂度低，同时限制较少，因此，在后续 的研究中被广泛采用，被称作g k 算法( 作者名称的前两个字母) 。在数据流值域 已知的情况下，c o r m o d e 与m u t h u k r i s h n a n 4 7 提出了一种新的解决方案，此方案 应用了甜甩f ，l 砌技术，空间复杂度为d ( 三l 。g ： u 1 0 9 坠魁型) 。其优点在于，算 占 口 法空间复杂度仅仅与值域相关，而与数据流中的实际数据项无关，能极大的降低 空间消耗，但是此算法也有缺点，在于其只能提供非精确的一致性近似结果，而 不能保证精确的近似结果返回。 论文 2 】【4 6 】中，研究人员关注的都是如何解决一致性近似下的序查询研究， 在分析了这些论文之后，同时结合数据流应用的实际背景，后序研究人员在此基 础之上提出了相对性近似下的序查询研究，并给出了多种解决方案。最早研究相 对性近似结果的g u p t a 与z a n e ，在论文【4 8 】中，他们提出了一个空间复杂度为 d ( 去l 0 9 2 ) 的随机算法，用于统计大量数据中排序出现倒置的次数。但是，i - d j 4 6 】 占 一样，此算法需要实现知道数据项数目，这也限制算法在数据流环境下的应用。 g r a h a mc o r m o d e 等人【4 1 1 解决此问题的方式是提出了有偏见的分位数概念 ( b i a s e dq u a n t i l e ) 。给定输入参数k ，唬，以及数组巾= 谚= 旅：1 f k ) ，返回结 果，一满足：掣占，结果的相似性是相对的，越大，谚越小，相似度也就 仍v 越高。此算法也有相应缺点，在论文【4 9 中，x u e m i nl i n 等人就证明，【4 1 】中的算 浙江大学硕士学化论文第2 章数据流序查询研究现状 法在部分实际数据应用中会失效，也是在【4 9 】中，他们提出了自己的解决相对性 近似序查询的方案。他们应用了g k 算法及多层次的采样技术，算法的平均空间 复杂度为d ( 去l o g ( 三1 0 9 吉) 号譬号笋) ，同时该算法也很好的解决了算法【4 l 】面临的 问题。此算法的缺点是，由于采用了采样技术，因此返回的结果是非精确的相对 性近似结果。有鉴于此，c o r m o d e 再接再厉，在论文 5 0 f p 提出了解决精确的相 对性近似结果的新颖算法。首先，他们假设数据流中的数据值域是固定的，例如 固定在值域u 中，在此假设基础之上，他们提出的新算法在性能上远远优于 【4 1 】【4 9 】，同时该新算法的空间复杂度也表现得相当出色，为d ( 塑掣l o g ( s 9 ) 。 前面提到的数据流序查询研究，都是基于所有的数据项，或者说是基于数据 流的界标模型( l a n d m a r km o d e l ) ，而x u e m i nl i n 等人在论文【5 1 】中，第一次提出 了基于滑动窗口模型的数据流序查询研究。在文章中，他们首先定义了两种滑动 窗口模型，分别为固定窗口大小模型与可变窗口大小模型，然后针对这两种模型 都提出了相应的解决方案。他们提出的解决方案，以g k 算法f 2 】以及e h 技术 ( e x p o n e n t i a lh i s t o g r a mt e c h n i q u e s ) 5 2 为基础。在此之后，a r a s u 和m a n k u 5 3 继 续了基于滑动窗口模型的数据流序查询研究。