（计算机应用技术专业论文）分布式数据流的topk查询研究.pdf

分布式数据流的t o p k 查询研究 研究生：刘维弋 导师： 金远平教授 学校名称：东南大学 摘要 近几年来，随着通信技术和计算机技术的不断发展，一种新型的数据模型分布式数据流， 得到越米越多的关注。它广泛应用于金融、网络监视、通信数据管理、传感器网络等众多领域。分 布式数据流除具有数据量大、数据到达速率快、数据无限性等特点外，还具有数据源分布、各个数 据源之间需要同步协调等特点。本论文主要研究分布式数据流环境下的t o p k 查询问题，即对分布 于不同地理位置的同一组对象的观测流数据进行分析，从而得到数值最火的k 个对象( t o p k 观测 查询) 。 首先通过实现一种基于滑动窗口的数据结构解决了数据流上的数据采集问题，将有效数据完全 存储于内存中，既满足应用的需要，又提高系统的响应速度和效率。其次，在分布式系统中的数据 传输方面，提出并实现了一种基于索引的c o u n t e rb l o o mf i l t e r 的算法，对传输数据进行有效的压缩， 从而降低分布式网络中的网络流量。最后，在对一种分布式t o p k 查询算法研究的基础之上，提出 并实现了一种新型的基于动态修正值的分布式数据流t o p k 查询处理算法。通过实验分析，该算法 在降低网络拥塞和网络负载方面有着突出的效果。 总之，本论文在分布式数据流环境下，对流数据的数据采集、数据压缩传输和分布式t o p k 查 询三个方面进行了研究，研究结果对于降低分布式网络负载、降低网络拥塞和提高分布式数据流系 统响应速度具有较好的理论和实用意义。 关键词：数据流，分布式网络，t o p k 查询 t o p kq u e r yo nd i s t r i b u t e dd a t as t r e a m s l i uw e i y i s u p e r v i s e db y p r o f e s s o rj i ny u a n - p i n g s o u t h e a s tu n i v e r s i t y a b s t r a c t i nr e c e n t y e a r s ，w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nc o m m u n i c a t i o n st e c h n o l o g ya n d c o m p u t e rt e c h n o l o g y , an e wt y p eo fd a t am o d e lc a l l e dd i s t r i b u t e dd a t as t r e a mh a sb e e nr e c e i v e dm o r e a n dm o r ea t t e n t i o n i t sa p p l i c a t i o n sc a l lb ef o u n di nm a n yf i e l d s ，s u c ha sf i n a n c i a la p p l i c a t i o n s ，n e t w o r k m o n i t o r i n g ，m a n a g e m e n to fc o m m u n i c a t i o nd a t a , s e n s o rn e t w o r ka n d s oo n b e s i d e s h a v i n gt h e d i s t i n g u i s h e df e a t u r e ss u c ha sl a r g ev o l u m eo fd a t a , h i g hr a t eo fd a t aa r r i v a la n du n l i m i t e dd a t a , d i s t r i b u t e d d a t as t r e a ma l s oh a st h ef e a t u r e so ft h ed i s t r i b u t i o no fd a t as o u r c ea n dt h en e e do fc o o r d i n a t i o no fa 1 1d a t a s o u r c ea n ds oo n t h i sd i s s e r t a t i o nm a i n l yr e s e a r c h e si n t ot h ep r o b l e mo ft o p kq u e r yo fd i s t r i b u t e dd a t a s t r e a m t h ekl a r g e s tv a l u e sc a l lb eo b t a i n e db yq u e r y i n gt h ed i s t r i b u t e dd a t as t r e a m s ( t o p - km o n i t e r i n g q u e r y ) f i r s t l y , w i t ht h ei m p l e m e n t a t i o no fad a t as t r u c t u r eb a s e do ns l i d i n gw i n d o w , t h ep r o b l e mo fd a t a c o l l e c t i o no fd a t as t r e a mi sr e s o l v e d t h ew h o l ev a l i dd a t ac a nb es t o r e di ni n t e r n a lm e m o r y a sar e s u l t , n o to n l yt h ea p p l i c a t i o n sc a nb es a t i s f i e d ，b u ta l s ot h es p e e do fr e s p o n s ea n de f f i c i e n c ya r ei m p r o v e d s e c o n d l y , t h i sp a p e rb r i n g sf o r w a r da n di m p l e m e n t sa na l g o r i t h mo fc o u n t e rb l o o mf i l t e rb a s e do ni n d e x f o rd a t at r a n s m i s s i o ni nd i s t r i b u t e dn e t w o r k b e c a u s eo fd a t ab e i n gc o m p r e s s e de f f i c i e n t l y , t h en e t w o r k f l o wo fd i s t r i b u t e dn e t w o r ki sg r e a t l yr e d u c e d l a s t l y , b a s e do nt h es t u d yo fad i s t r i b u t e dt o p - kq u e r y a l g o r i t h m ，an e wt y p eo fd y n a m i ca d j u s t m e n tf a c t o rb a s e da l g o r i t h mf o rt o p - km o n i t o r i n gq u e r ya r e p r o p o s e da n di m p l e m e n t e d b ya n a l y z i n gt h er e s u l t so fe x p e r i m e n t ，t h en e wa l g o r i t h mc a nb es h o w nt o h a v eo u t s t a n d i n gr e s u l t si nr e d u c i n gn e t w o r kc o n g e s t i o na n dn e t w o r kl o a d t os u mu p ，t h i sd i s s e r t a t i o nd o e ss o m er e s e a r c hi nd a t ac o l l e c t i o no fs t r e a m i n gd a t a , c o m p r e s s i n g t r a n s m i s s i o no fd a t aa n dd i s t r i b u t e dt o p kq u e r y t h er e s u l t so ft h e s es t u d i e sa r es i g n i f i c a n tb o t h t h e o r e t i c a l l ya n dp r a c t i c a l l yt or e d u c i n gd i s t r i b u t e dn e t w o r kl o a d ，b r i n g i n gd o w nn e t w o r kc o n g e s t i o na n d e n h a n c i n gt h es p e e do fr e s p o n s e k e y w o r d s ：d a t as t r e a m ，d i s t r i b u t e dn e t w o r k , t o p kq u e r y 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签名： 型维墨日 期：21 窆：! 1 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名：垄维盔导师签名： 日 期： 2 田多- ；、j 第一章引言 第一章引言弟一早 ji 面 尽管d b m s 技术和d w 技术获得了巨火成功，但是从上个世纪末开始在一些新犁应用中出现的数据 却对传统数据处理技术提出了新的挑战。这些数据包括网络数据包数据、网站的访问日志数据、传 感器的观测结果数据、电话记录数据等，并且其数量仍然在不断地增加。下面举两个应用例子。 1 、网络监测应用： 随着网络的发展，网络应用也渗透到社会中的每一个领域中。网络也同时成为不法者的攻击目 标。某些网络用户为达到自己的某些私利，对网络上的计算机主机进行攻击。其中攻击的方法多种 多样，最为普遍的攻击形式应属d o s d d o s 攻击。d o s 叩o s 攻击可能会产生异常多的从单个i p 地址发 到多个分布式d n s 服务器的d n s 服务请求。在接收端，瞄准i s p 私有网络中个别主机的d o s d d o s 攻击的 特征是在几个i s p 的边界路由器上产生大量的通信量，而这些流量的目标是一个单独的主机。 因此为了防备d o s d d o s 攻击，我们需要观测这些网络传输数据，观测的内容有如一f j l 种： 近一段时间内，哪个i p 地址的人量s y na c k 没有返回的服务器主机。 近一段时间内，哪个i p 地址进行频繁的d n s j j 艮务请求。 近一段时间内，哪个网络上的数据包频繁丢失。 近一段时间内，哪个服务产生的数据流量最大。( 注意，可以通过不同的端口号来区分不同 的应用) 。 2 、传感器网络 随着通信技术、嵌入式计算技术和传感器技术的飞速发展和日益成熟，具有感知能力、计算能 力和通信能力的微型传感器开始在世界范围内出现。由这些微传感器构成的传感器网络引起了人们 的极大关注。这种传感器网络综合了传感器技术、嵌入式计算机技术、分布式信息处理技术和通信 技术，能够协作地实时监测、感知和采集网络分布区域内的各种环境或监测对象的信息，并对这些 信息进行处理，获得详尽而准确的信息，传送到需要这些信息的用户手中。传感器网络可以使人们 在任何时间、地点和任何环境条件下获取人量详实而可靠的信息。因此，这种网络系统可以被广泛 地应用于国防军事战争、国家安全、自然环境指数监测、交通管理、制造业、反恐抗灾等领域。 传感器网络中具有代表性的查询如下： 如果某一个地理位置的周围的儿个传感器报告的测量值超出给定的正常值域，则发出警报。 分析各传感器发来的数据，经处理后得到准确的测量结果，为做出及时、合适的决策提供依 据。 对某移动物体实时观测，及时准确地返回被观测的移动轨迹。 在灾难救援中，依靠散布大量的微型传感器来监测灾难事故中的各项信息指标，为灾难救援 人员提供可靠的信息，从而保障灾难救援人员的人身安全。 上述例子具有两个共同特点。首先，从数据的角度来讲，数据量极大而且数据产生速率非常快。 其次，从应用的角度来讲，要求获得实时、连续的查询结果。传统的数据处理技术由于需要首先将 所有的数据存到存储介质( 磁盘或者内存) 中，然后再进行查询处理，不适合处理这类应用。因此有 必要专门为这类应用开发新的数据处理技术。 东南人学硕士学位论文 1 1 数据流 1 1 1 数据流及其产生背景 在许多应用领域中，数据不是以有限的数据集合的形式存在，而是以持续、大量、迅速、事先 不可预知的形式产生。数据流是以连续的、有序的“流”的形式输入的数据。与数据流概念相关的 新的应用领域包括：网络安全、金融领域、工业生产监测等。在这些领域中，数据流信息直接反映着 现场的工作状况，并作为管理操作的重要依据。一旦信息丢失、损坏或处理不够及时，将会对系统 造成严重的损失，甚至是破坏。对这些数据实时进行查询和监测是必须和重要的，同时要求数据反 馈的速度迅速，能够对特定的查询及时做出响应。 特别要提出的是，近几年来，一些以传感器对监测系统进行数据采样、用计算机进行处理的应 用己受到越来越多的重视口1 。在整个网络系统中建立多个数据采集点，并安装传感器，利用低级网 络协议进行数据传输，收集传感器所获取的数据，从而进行系统监控和数据分析等工作。当今这样 的t 程己经与我们非常的接近，数据计算和传感器在我们生活的诸多方面都提供着很多帮助。传感 器数据采集系统将产生大量的数据，这些数据直接反映出工作现场的情况，有待进行分析和处理。 对传感器采样数据进行处理和查询是非常必要的。显而易见，处理传统数据的过程、语言和操作的 能力对于这种传感器采样获得的数据是不适合的，由此，一种新的数据处理方式的产生是必需的。 在典型的基于计算机的数据采集系统中，数据来自于各种各样的监测装置和传感器，它们将未 经加工处理的现场数据通过有线网络或无线网络源源不断的传送给计算机，形成了数据流。 对此进行抽象，人们提出了数据流的概念h 1 。数据流是以连续的、有序的“流”的形式输入的 数据，即将这种不断产生的、大量的、迅速的、不确定的数据源称为数据流。 形式上，一个数据流是一个按照时间递增顺序排列的无穷元素序列s = s ，s z ，s t ，一， ， s 。是时刻t 出现的序列元素畸1 ：它们按照i 刮定的次序产生，具有特定的时间间隔，不被人为终l l 二或扰 乱。一个数据流也可以被视做是对一个长度为d 的数组a 0 d 1 不断维护的过程。数据流上的每一 个元素s 。都会改变数组a 的内容。例如，一个商业网站总共有d 个网页，网站经理要求能够实时监控 各网页的访问流量。我们首先为所有的网页从0 到d 一1 编号，然后再创建一个长度为d 的数组 a o d 一1 。当第i 个网页被点击一次时，a i = a e i 十l 。在这个例子中，数组的长度等于数据流中 元素的数目( 每个元素更新对应网页的点击次数，因而元素数目等于存在的网页数目) ；数组中的每 一项a i 对应于数据流中某内部元素的一个值。 数据流与传统的数据源之间存在许多不同点，主要表现在数据产生方式、接收数据处理方式、 数据管理模式和管理系统等多个方面的差别。数据流的特点如下： 1 、数据量人，甚至无限。 2 、数据到达的速度快。 3 、数据变化毫无规律可循。 4 、数据处理要求快速的响应。 1 1 2 数据流的分类 根据数据流对数组a o d - 1 的不同影响方式，数据流模型可以划分为三种子模型：时间序列模 型( t i m e s e r i e sm o d e l ) 、收银机模型( c a s h r e g i s t e rm o d e l ) 和转盘模型( t u r n s t i l em o d e l ) 哺1 。 1 时问序列模型： 在这种模型中，数组a 中各项的值被依次修改。换句话说，数据流上的元素s 。必然改变a i 的值， 这也意味着a i 的值仅被改变一次。该模型主要出现在时间序列数据中。一个典型的例子是监控一 2 第一章引言 只股票报价的数据流，例如每分钟纳斯达克( n a s d a q ) 成交量。另外的例子是网站项目点击率监控 与分析，每隔1 小时汇报过去l 小时内所有用户点击各个固定项目链接的次数。 2 收银机模型： 在这种模型中，数组a 中各项的值不是按序变化的，但是每次变化都使项值增加。例如，在某一 个电子商务的网站上，浏览该电子商务的网站的用户点击自己感兴趣的商品并进行详细查看。此时， 该电子商务网站系统将实时记录该用户此次登陆所浏览过的所有商品。系统可以创建一个长度d 为 6 9 7 亿1 的数组a ，世界上每一个网络用户都可以在这个数组中找到对应的项。当某一个网络用户退出 登录后，系统将找到数组中属于这个人的项( 假设为a i ) ，然后a i 中将对应的商品的项的点击次 数进行更新，这里的更新当然仅仅包括增量的更新( 因为点击次数只能增加) 。 3 转盘模型： 这种模型是受拥挤的地铁站中记录乘客出入十字旋转门的启发而产生的，数组a 中各项的值并不 是按序变化的，而且每次变化中其项值可能增加，也可能减小。转盘模型的条件比上述两个模型的 条件都宽松，也比较常见。例如，地铁公司想监控每一个地铁站中乘客的进出流量情况，则进出地 铁的乘客就成为一个数据流。首先，该公司可以创建一个包含d 个地铁站的数组a 0 d - 1 。当有一 个乘客进入某一个地铁站后，该地铁站所对应的数组项( 假设是a i ) 加1 ，即a i = a i + 1 ；若有一 个乘客由该地铁站出来时，则a i = a e i 一1 。 数据流模型除了按照数组a 的不同变化方式分为上述三种子模型之外，还可以按照数据流上各个 元组的重要程度的不同划分为另外三种子模型：界标模型( l a n d m a r k m o d e l ) 、滑动窗口模型( s l i d i n g w i n d o wm o d e l ) 和衰减窗口模型( d a m p e dw i n d o wm o d e l ) 。 1 界标模型： 在这个模型中，数据流算法仅仅考虑从某一个特定时间点s 开始到当前时间点n 之间的所有数据， 查询范围是： s n 。换句话说，在范围 0 s ) 之间的元素，其重要性为零；在范围 s n 之间的 元素，其重要性均相等。 2 滑动窗口模型： 令w 为窗口大小。在这个模型中，数据流算法仅仅考虑最近的w 个元素。即其查询范嗣是： m a x ( 0 ， n w + 1 ) n 。处在查询范围之外的元素，其重要性为零；处在查询范围之内的元素，其重要性均相 等。滑动窗口模型注意到了新旧元素的不同地位，旧的元素不断被淘汰，不再参与计算。 3 衰减窗口模型： 在这个模型中，数据流算法的范围从初始时间点到当前时间点，查询范围是： 0 n 。但是，处 在查询范围中的各个元素的重要程度是不相同的。新到达的元素，其重要程度较高；旧到达的元素， 其重要程度较低。例如，令a v g 。是一个平均数，x 是新到达的元素，衰减系数是p ，0 p t 。样本集合中的各个元素均以概率t t 被消除，从而有空闲的空间以便存放新数据。精确采样方法通过逐步提高参数t 的值，实现数据流上 的均匀采样。 数据流问题的采样有两个难点，第一，采样并不是解决许多问题的强有力的基础。一 些复杂的分析所需的远远不仅仅是采样。第二，采样方法不能应用在转盘模型中，如果 数据流展开的时候，所维持的采样集被算法删除，则会被迫再从过去的数据中进行采样，这 在实践中是不可行的。 1 1 3 3 小波方法( w a v e l e t ) 小波分析方法是一种通用的数字信号处理技术。类似于傅立叶变换，小波分析根据输入的模拟 盆变换成一系列的小波参数，并且少数几个小波参数就拥有大部分能量。根据这个特性，可以选择 少数小波参数，近似还原原始信号。 1 1 3 4 哈希方法( h a s h ) 定义一组哈希函数，将数据从一个较大范围映射到另一个较小范围中去是计算机领域的一个常 用手段。本小节介绍两种利用哈希函数生成概要数据结构的方法：b l o o mf i l t e r 和刚方法。 b l o o mf il t e r - b l o o mf i l t e ru 1 1 自从1 9 7 0 年被提出来之后，就被广泛应用于网络、数据库，p 2 p 系统等众多领域。 该算法的最大特点是仅使用一小块远小于数据集数据范围的内存空间表示数据集，并且各个数据仍 然能够被区分开来。假设所申请的内存大小为m 比特位；该方法创建k 个相互独立的哈希函数，能将 数据集均匀映射到 1 m 中去。对任何元素，利用哈希函数进行计算，得到k 个 1 m 问的数，并将 内存空间的这k 个对应比特位都置为l 。这样，就可以通过检查一个元素经过k 次哈希操作后，是否所 有对应的比特位都被置l 来判断该元素是否存在。这种判断方法可能会产生错误虽然某元素并不 存在，但是它所对应的k 个比特位都已经被其他元素所设置了，从而导致被误认为存在。庆幸的是， 这种错误发生的概率随着内存的增加可以变得非常小。 5 东南大学硕上学位论文 由于本文参考b l o o mf i l t e r 技术，提出了一种新型的概要数据结构，在后面的章节中本文将继 续对b l o o mf i l t e r 做详细介绍。 f m 方法( f l a j o l e t - m a r t i n ) ： f m 方法是求解数据集中的相异元素个数的有力手段。它所采用的哈希函数( l e a s ts i g n i f i c a n t1 b i t ，l s b ) 将一个大小为m 的数据集映射到范围 0 l o g ( m 一1 ) 中去，而且映射- i l i 的概率是l ( 2 1 + 1 ) 。 假设相异元素的个数是d ，且哈希函数独立随机，则恰有d ( 2 1 + 1 ) 个不同元素映射到i 。这个性质可以 用于估计d 的值。在文献 1 2 中，作者扩展了f m 方法，在对多个数据流做复杂的集合操作之后，能够 得到结果集合上的不同元素的个数。 1 1 3 5 基于滑动窗口模型的方法 在滑动窗口模型下构造概要数据结构比在界标模型下更具挑战性的原因在于不仅新元组不断到 达，而且旧元组会过期。因此，如何处理过期数据，使得查询结果一直可靠就成为一大难题。滑动 窗口是数据流上应用比较多的一种特殊的数据抽样方法。滑动窗口是指在数据流上设定一个区间， 该区间只包括数据流中最近到来的那部分数据。随着新数据的到米，窗口向前移动，用最新的数据 替换最旧的数据。与其他的抽样方法相比，滑动窗口的优点在于语义明确。更重要的是在许多应用 中，例如传感器网络，用户关心的只是数据流中新近到米的那部分数据。此时，滑动窗口是一种十 分理想的抽样方法，通过滑动窗口对连续的查询范嗣的限定，包括两种限定方式：一种是窗口中包 括最近到来的t 个元组，称为基于顺序或基于计数限定的滑动窗口。另一种是窗口中包含最近t 个时 间单元内到来的元组，称为基于时间限定的滑动窗口。 基本窗口( b a s i cw i n d o w ) ： 基本窗口技术将窗口按照时间次序划分成大小相等的子窗口，称为基本窗口，如图1 2 所示。如 果窗口大小为w ，子窗口的个数为k ，则每个基本窗口包含w k 个元素，且每个子窗口存在一个“小结 构”表示该子窗口的特性。如果某个子窗口内所包含的所有元素都已经过期，则删除表征这个基本 窗口的小结构。用户可以基于这些未过期的小结构得到查询结果。曾经有相关的文献采用这种方法， 快速地从众多股票中得到相关的几只股票。 l llililli 基本窗口基本窗口基本窗口基本窗口 整个滑动窗口 图1 2 滑动窗口中的基本窗口 指数直方图方法： 在滑动窗口计算模型中，指数直方图方法是一个很重要的方法，它最早用来生成基于滑动窗口 模型的概要数据结构。传统的直方图方法将数据集划分成多个桶，相邻桶的元素值连续；而指数直 方图则是按照元素的到达顺序构建桶，桶的容量按照不同级别旱指数递增，从小到大分别是1 、2 、4 、 8 、1 6 、3 2 、，且各个级别桶的个数均不超过一个预定义的阈值。每当新的元素到达时，就可能 根据不同的应用需求来决定是否创建一个最低级别的桶。 6 第一章引言 1 2 分布式数据流 在上面提到的数据流应用中，存在一种更加特殊的数据流- = 分布式数据流。分布式数据流， 即数据源分布于不同地理位置的数据流集合。通常情况下，由于应用的要求，虽然各数据流的数据 源不同，但都需要在同一个地理位置对数据流集合进行处理，因而产生了对于分布式数据流的研究。 1 3 分布式数据流的应用实例 本节详细介绍一些数据流应用例子( 很多例子可在数据流查询资料库n 3 1 中获得) ，以此说明数 据流研究的重要性。 道路交通情况的监测： 城市车辆拥有量的急剧上升，给城市交通带来了巨大的压力。为了缓解城市中交通堵塞的情况， 提高城市道路的畅通程度和利用率，人们可以将各种监测装置布置于城市各交通要道，对交通状况 进行实时的监测，并将监测数据不断地送往监测中心。在监测中心实时对到来的数据进行计算和分 析，对道路进行有效、快捷的交通引导。 传感器网络： 传感器网络是一个成长很快的研究领域1 ，被广泛应用在地理监视、高速公路拥塞监测、移动 物体跟踪、生命信号的医学监测和制造业流程监管等应用中。在一个传感器网络中分布着众多的传 感器节点( s e n s o rn o d e ) 。传感器节点间通过发射无线信号进行通讯，并最终将数据传送到中心主机 中进行处理。用户可以持续分析传感器节点采集的数据，发现异常模式，及时给出报警信号。 自然环境状况的监测：随着工业化和现代化水平的不断提高，人类的生产和生活等方面给自然 环境带来了越来越多的危害。因此对自然环境状况的密切追踪也就成为一项重要的工作。对自然环 境状况的监测中，一个典型的例子就是对水资源的监测。工业和生活污水会给各河流湖泊带米不同 程度的污染，对于这些河流湖泊的污染情况的监测对饮用这些水源的人们的身体健康来说有着极为 重要的意义。在这类监测中，无数多个传感器被放剑各水源中，对水中的各种元素含量进行实时监 测。当危险元素超出正常水平时，监测系统会发出警报及时提醒人们采取适当的措施提高水源的饮 用安全性。 电信通信分析： 信息化时代的到来，随着社会各个体通信的频繁，大量的通信记录也随之产生。如何充分的利 用这些信息，为社会创造更多有用的价值成为一个研究领域的课题。在这种应用背景中，大量通信 记录从不同的数据源处涌涌而来，如何及时地分析这些数据流成为一个研究的难题。通过对数据流 的分析，我们可以得到某个通信个体的行为特征，以此产生适合该通信个体的服务。这些通信信息 包括：网站点击日志，电话通信记录，网络流量日志，网络客户的行为日志等。 解决传统问题： 数据流领域的研究成果能够应用到传统数据库研究领域中去。在关系数据库的杏询优化( q u e r y o p t i m i z a t i o n ) 和近似查询应答( a p p r o x i m a t eq u e r ya n s w e r i n g ) 中，都需要维护相关数据集合的统 计信息，例如，计算某一列中相异元素个数、创建等宽直方图( e q u a l d e p t hh i s t o g r a m ) 、创建v 一 优化直方图( v o p t i m a lh i s t o g r a m ) 等。针对这些问题的早期解决方案都需要扫描整个数据集合。数 据流领域的研究成果为这些问题提供了更新、更好的方法。这些方法维护一个概要数据结构 ( s y n o p s i sd a t as t r u c t u r e ) ，每当数据集合发生变化( 插入一个新元素，或者删除一个已有元素) 时，更新概要数据结构的内容。用户可以基于概要数据结构获取数据集合的统计信息。这些方法的 7 东南大学硕上学位论文 空间复杂度和时间复杂度都不高。 另外，数据流领域的研究工作还可以被用于解决涉及外存( 含光盘、磁盘、磁带等) 的问题。在 某些应用中，由于数据量非常庞大，不可能一次性将数据全部从外存载入到内存中，只能够设计一 次或者多次遍历算法来解决问题。我们可以对该数据集合做一次遍历，自动产生数据流，从而使得 针对数据流模型的算法能够扩展到这些应用中去。简而言之，数据流算法能够对超大数据集合进行 离线分析( o f f l i n ea n a l y s i s ) 。 1 4 分布式数据流所面临的困难与挑战 和传统数据模犁相比，数据流模型具有截然不同的特性，这对数据流模型下的查询处理技术提 出了新挑战。概括言之，主要有以下几个方面的挑战： 实时性( r e a l t i m e )实时、连续地输出查询结果是数据流算法最基本的要求。对于数据流上 到达的任一元组( t u p l e ) ，要求数据流算法能很快处理完成。否则，数据不断到达、延时不断积累， 最终导致服务质量q o s ( q u a l i t yo fs e r v i c e ) 显著降低。另外，在大多数应用里，数据流速率会随着 外部环境的变化而改变。例如，节假日的信用卡消费日志要比- 丁作日的日志火很多。如何在数据流 速率突然加快的情况下，仍然实时输出查询结果是一个重要的研究课题。 低空间复杂度( 1 0 ws p a c ec o m p l e x i t y )前面一节提到，数据流规模在理论上是无限的。为保 证算法持续稳定运行，数据流算法的空间复杂度要非常小。假设在当前时刻，数据流的长度是n ，数 据流算法的空问复杂度一般要求在0 ( p o l y ( 1 0 9n ) ) 2 之内。这样的话，数据流算法的空间占用量的增 长速度就远远小于数据流自身规模增长的速度。另外，有些数据流算法的空间复杂度和数据流的长 度无关，仅仅和数据流上相异元素的个数有关。假设数据流上相异元素个数不超过m ，则空间复杂度 被限制在0 ( p o l y ( 1 0 9m ) ) 之内。例如，目前冈特网采用i p v 4 协议，总的i p 地址数目不超过2 3 2 个3 。即 使以后采用了i p v 6 协议，总的i p 地址数目也不超过2 1 2 8 个。注意：l 0 9 2 船= 3 2 ，l 0 9 2 1 2 8 = 1 2 8 ，都很小。 综合来说，数据流算法的空间复杂度一般是：0 ( p o l y ( 1 0 9n ，l o gm ) ) 。 结果准确性( a c c u r a c y )数据流模型下，数据规模大、速率快，对于一些复杂问题不可能一次 遍历就得到准确答案。幸运的是，很多实际应用也并不需要误差为零的查询结果。例如，网络路由 器通过实时监控各个i p 地址发送的数据包数量，可以检测是否有d o s 攻击。对路由器来说，i p 包数日 到底是5 0 1 7 5 还是5 0 0 0 0 士1 0 0 0 ，差别并不大。数据流算法的一大特性就是它通常返回一个近似值，而 非准确值。算法的精确度往往和内存空间紧密相关，当被分配更多内存空间时，算法准确度也就更 高。 适应性( a d a p t a b i l i t y )在很多应用中，数据流变化很大。这种变化不仅可以是流速变化，还 可以是数据分布的变化。例如，在传感器网络中，各个传感器节点都采集数据，发送到中心主机进 行处理。传感器节点发送数据的速率和外部条件紧密相关，当特定事件发生时，有些节点会发送更 多数据。对于数据流算法而言，当外部条件发生变化时，能够根据数据流变化调整参数，进而提高 性能就非常重要。 2 p o l y 在这里表示一个多项式( p o l y n o m i a l ) 函数。 3 i p v 4 和i p v 6 是两种i p 层协议。i p v 4 采用3 2 位地址长度，只有约4 3 亿个i p 地址。i p v 6 采用1 2 8 位地址长度 几乎可以4 i 受限制地提供地址。按照保守方法估计i p v 6 实际可分配地址，整个地球每平方米面积上可分配1 0 0 0 多 个地址。 8 第一章引言 1 5 关于本文 1 5 1 本文的贡献 论文针对分布式水果销售系统的应用背景，提出了分布式数据流t o p - k 查询优化方法。该系统描述如 下： 一家水果销售总公司在城市的不同地点设有m 个水果销售点，每个水果销售点都同时销售同样 的f 种水果。为了对水果的采购和分配进行统一调度和控制，总公司需要对这f 种水果的销售数据 进行实时监控。 在对象众多的实际应用中，人们不可能也不需要对全体对象都进行实时控制，所关心的对象只 是它的一个子集。因此我们只需以某种排序标准为依据对分布式数据流进行分析，从而查询出在排 序结果中位于最前列的k 个对象( 分布数据流t o p - k 查询) ，并进行控制。分布数据流t o p k 查询， 即通过对分布式数据流的杏询，返网具有最人数值的k 个对象。在上例中，水果销售总公司只需实 时查询全市范围内销售量最高的k 种水果，以优化资源配置，保证这k 种水果的供应。 论文针对该应用背景进行了分布式数据流环境下的t o p - k 查询相关研究，目的是降低该分布式系统中 的网络流量，从而降低整个网络的负载，进一步提高系统的效率。具体研究贡献如下： 1 、进行流数据的采集。 在研究中，每一个分布结点，即每一台销售主机都是一个独立的数据采集和预处理子系统，它 负责进行销售商品的记录和简单地数据处理。这些分布结点所要处理的销售商品的数据并不是静态 地存储于数据库，而是随着时间以一种流的方式持续不断的到达。在对该流数据处理之前需要对其 进行存储，以便进行数据处理工作。因为各分布式子系统内存的限制，不可能将所有数据存储于内 存中( 流数据的数晕是无限的) 。通常的方法是将其存储于硬盘之上，在需要读取数据的时候再进行 数据奄找。由于硬盘属于机械设备，它的存取速度与内存相比速度极慢，无法满足数据流应用中数 据快速到达和实时处理的需要。因此本文提出了一种高效的滑动窗口式数据结构，将有效数据暂存 于内存中，从而提高系统的响应时间。在数据失效且分布式子系统空闲时将其转存于硬盘中，以便 未来的非实时性的数据处理。最后本文通过实验数据分析说明了该采样方法的有效性。 2 、进行流数据的压缩。 为节约内存空间和降低网络负载，一般考虑采用流数据的压缩数据结构来存储流数据。本文在对 b l o o mf i l t e r ( 简称b f ) 分析的基础上，提出了一种基于索引的c o u n t e rb l o o mf i l t e r ，简称i c b f 。 i c b f 扩展了b l o o mf i l t e r 的功能，它除具有数据压缩的功能外，还可以记录存储在i c b f 中的每个 元素的数目。i c b f 相对于b f 的优点有：首先，i c b f 打破了b f 采