（计算机应用技术专业论文）面向位置服务的空间数据流处理技术研究.pdf

摘型 摘要 攮于虚簧的服务迎过特定t 门定缸技术获得移动终端的地理位置信，色、，提d ! 给移动用户本人、通信系统或第三方，为移动刖户提d i 与其位簧相关的丰寓多彩 i i j 应用。在这种应用“t ，移动终端n 0 位蚩数据源滁不断的流入数据库系统，更新 移动终端的位置，因此基于位黼的服务的数据更新频率较快，属于一种高动态的 数据应用土1 ：境。另外，箍于位筒f j j l l 务在某些场合需要实时的处理。 传统的数据库采用一种持久存储、一次查询的数据处理模式，已经不能适应 现在大量的，包括基于位置服务在内的实时在线的新兴应用，这一类应用的特点 是：数据到达过程是连续的，数据的查询处理是实时的。因此适合此类应用的数 据流系统应运而生。数据流系统以连续查i 句为特点，连续查询的处理机制能够傈 汪数据处理做到实时处理。但是现有的通用的数据流系统没有对空问数据处理的 支持，而基于位筠：服务显然是一种需要空m 数据处理的应用。 本文从支持位罱服务的后台数据处理发，提出用基于数据流系统的流数据 库来支持基于位置服务的数据处理的思想，并结合当今数据流系统的发展和基于 位置n j 服务的需求，列数据流系统进行空间扩展，提出一种空间数据流系统的模 型。此模型通过：( 1 ) 增加空问数据类型，束表示基于位置服务中空间对象，( 2 ) 增加空问消同和空m j i i 函数，使得数据流系统能够提供空问的连续查询。基于此模 型的位置服务的数掂处理，通过其内在的空问连续查询，能够让基于位置的服务 真正做到对位置数据流的实时处理。基于此模型构建的基于位置服务的数据处理 实验的结果证明，其能够为基于位置服务提供数据处理的支持，通过性能分析也 i 正明其在处理基于位置服务的数据时，相比较于传统数据库有一定的优势。 关键词：基于位置的服务，数狮流，空间连续查洵 a b s t i i c a b s l l l a c t t h ei o c a t i o r lb a s t e is e l v i c e s g e t t i l ei o c a t i o ni n f o r n l a f i o n b yu s i n gg lx 7 e n p o s t i o n i n gt e c h n i q u e t h e np l o v i d et h i s i r l f o t m a r i o nt om o b i l et l s c l ，c o n m m n i c a t i o n s y s t e mo i t h i r d p a r t 3 7 s e r x 7 i c e sp r o x 7 i d e ra n db r i n gav a r i o u so fl o c a t i o n b a s e d a p p l i c a t i o nt om o b i l et l s e l t i l el o c a t i o ni n f o l m a r i o no f m o b i l et e n n i n a lc o n t i n u o u s l y a r r i v et h ed a t a b a s es y s t e ma n dt h e nu p d a t et h el o c a t i o no f m o b i l et e r m i n a l ，s ol o c a t i o n b a s e ds e r v i c e sh a v eh i g hf r e q u e n c yo fd a t au p d a t i n ga n di sak i n do fh i g h l yd y n a m i n c e n v i r o n n l e n l si na d d i t i o n ，t h el o c a t i o nb a s e ds e r v i c e s r e q u i r e r e a l t i m ed a t a p r o c e s s i n gi ns o m ec a s e s t r a d i t i o n a ld a t a b a s eh a sad a t ap r o c e s s i n gm o d e li nw h i c ha l ld a t at ob em a n a g e d t a k es o m ef o n n o fp m s i s t e n td a t as e t sa n do n e t i m eq u e r y f o rm a n yr e c e n t a p p l i c a t i o n s ，i n c h l d i n gl o c a t i o nb a s e ds e r v i c e ，t h ec o n c e p to fac o n t i n u o u sd a t as t r e a m i sm o r ea p p r o p r i a t et h a nad a t as e tt i l ec h a r a c t e r i s t i co ft h e s ea p p l i c a t i o n si st h a tt h e d a t ac o n t i n u o u s l ya r r i v e sa n dt h eq u e r yp r o c e s s i n go fd a t ai sr e a l t i m ea n ds ot h e d a t as t r e a ms y s t e mw h i c hs a t i s f i e st h ed e m a n do fd a t ap r o c e s s i n go ft h i sn e wt y p eo f a p p l i c a t i o n st h ed a t as t i e a r ns y s t e mh a st h ec h a r a c t e r i s t i co fc o n t i n u o u sq u e r yw h i c h c a np r o v i d er e a l t i m ed a t ap r o c e s s i n gt h ee x i s t i n gg e n e r a ld a t as t r e a ms y s t e md o e s n o ts u p p o r ts p a t i a ld a t ap r o c e s s i n g ，b u tl o c a t i o nb a s e ds e r v i c ea p p e a r n t l yr e q u i r e s p a t i a ld a t ap r o c e s s i n g t h i sp a p e rp r o p o s e dt h em e t h o dw h i c hi m p l e m e n t sl b sa p p l i c a t i o n sb ys t r e a m d a t a b a s eb a s e do nd a t as t r e a ms y s t e mf r o mt h ed a t ap r o c e s s i n gv i e w f u t h e r m o r e ，t h i s p a p e re x p a n d st h es t r e a l nd a t a b a s et os u p p o 九s p a t i a lo p e r a t i o nw h i c hc a np r o v i d ed a t a p r o c e s s i n gf o rl b sa p p l i c a t i o n sa n ds a t i s f yt h er e q t f i r e m e n to fl b sa p p l i c a t i o n sa n d f i n a l l yp r o p o s e dam o d e lo fs p a t i a ld a t as t r e a ms y s t e m t h i sm o d e le x p a n d st h e g e n e r a ld a t as t r c a n ls y s t e mb y ：( 1 ) a d d i n gs p a t i a ld a t at y p et os u p p o r ts p a t i a lo b j e c to f l o c a t i o nb a s e ds e r v i c e s ，( 2 ) e x t e n d i n gt h ec o n t i n u o u sq u e r yb ya d d i n gs o m es p a t i a l p r e d i c a t ea n ds p a t i a lf o n c t i o n t o s u p p o r ts p a t i a lc o n t i n u o u sq u e r y b a s e do n t h i s m o d e l ，l o c a t i o nb a s e ds e r v i c e c a n r e a l t i m e l y h a n d l el o c a t i o ni n f o r m a t i o n p r e l i m i n a r ye x p e r i m e n ta n dp e r f o r m a n c ea n a l y s i sa l s os h o w st h i sm o d e lc a r ls u p p o 九 t h ed a t a p r o c e s s i n g o fl o c a t i o nb a s e ds e r v i c e sa n dh a sm o r ea d v a n t a g e st h a n t r a d i t i o n a ld a t a b a s e t 天i i l l ： uj 、h ! 沦义 独创性声明 小人声l 所呈交的学沦文是术人庄导师指导下进行的究r f t - 及耿得i 佝 研究成果。据我所知，除了文| = | = | 特别：l j 以十, j i i _ i ：垌i 致谢的地方外，沦义叶，不包含其 他人已经发表或撰写过的研究成果，也不包含为获得重庆邮1 乜大学或其他教 育机构的学位或证书而使用过的材料。与我一i 司：i 二作的同志列本研究所做的任何 贡献均已在论文中作了明确的晚明并表示跗意。 学位论文作者签名 卉泣款 签字| = f 期： 一，年月g 日 学位论文版权使用授权书 本学位论文作者完全了解重庆邮电大学有关保留、使用学位论文的 规定，有权保霞f 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被 查阅和借阅。本人授权 重鏖自鱼盔堂 可以将学位论文的全部或部分内容编 入有关数掘库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位 论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 曹谊袈 翩签名：忆伽一 签字| = 1 期： 知p 年f 月留| = f 签字日期：力柙年彳月乒日 第一章绪沦 1 1 研究背景 第一章绪论 在无线宽带网和移动汁算上取得的进步使得基于位置的服务( l o c ul i 0 1 1 b a s e ds o l v ic 。，l 盼) ，作为一种电信运营商提供的增值业务，随之出现。l l 粥 使电信运营商能够使川自己的无线网络5 i 台，给客户提供个性化的位置相关的内 容【| i 。除了电信运营商，更多的j 】i 务提供者，睹如无线局域网提供者，企业和其 他组织正在为客户羽i 员：i 矧：发和川j 置位罱相关的服务，以便取得更大的收益和生 产力。 早在1 9 9 6 年，美国联邦通信局( ：ec 1 e f 8 lc o l l i i i l i l l l c ul i o n sc o m m i s sl o n ，f c c ) 就已经发巾了一项名为e 9 i1 的法案吵要求通信运营商提供向客户提供基于位 置的无线紧急服务。这种j j 【i l 务可以使客户在遇到诸如火灾、安全等紧急情况时， 能够提供其所在的位战信息，以减少用户的损失。这项法案也促进了l b s 的应用。 i 。b s 应用的实现涉及到很多方而的内容，包括定位技术1 3 | i ”、数据处理、服 务类型【l i 、隐私保护，系统架削6 1 川等，这些方丽的因素都影响着l b s 能否取得广 泛的应用。在这些l 刭素中，数据处理显得尤为重要，一种好的数据处理机制可以 使l b s 应用获得较好的性能表现，并且随着i 。i 搭应川的服务容量的增加，能够高 效进行数据处理的机制变得更加的重要。 现在，国内已经有很多的运营商羽i 应用提供商提出或者部署了自己的l b s 实 现平台1 6 i i ”，它们的 s 的应用大都是一些简单的应用，并且也仅仅一种小范围 的运用。在这种范围的应用中，对i 。b s 数据处理的支持大都是基于传统数据库的， 不能很好的提供实时处理的后台数据处理机制，虽然这类机制基本能够胜任，但 是对于将来的大规模的应用，这种机制在某些方面存在不足，因此对一种符合 l b s 应用特点的i 高效的l 。b s 应用实现机制值得进行深入的研究。 1 2 研究内容 本论文通过对l b s 应用的特点进行分析，着眼于l b s 应用需要的数据处理机 制，探讨l b s 应用的实现方式。并在此基础上提出使用数据流系统【8 i ，对这种应 用提供后台的数据处圳支持。接着本文基于现有的数据流系统模型，进行空川操 作的扩展，提出一利，新的l b s 应用的实现方式。本论文的研究工作如下所示： 1 通过分析i 。b s 应用的特点，晚明传统数据库在实现这种应用时的不足。 第一章绪沦 2 在第部分f 作的离i 分昕数据流系统为适合l 吣应刷的实现并提 划数据流系统进行，孙lj 扩m i ；f 、要一陀。 - 分忻丁对数槲流系统进盯。孙1 雁涉及剑n q 圳题例步陶建出一个守川数 抓流系统的馍型。 小通过编程实现个空m 数据流系统的漠型- j i 最终基于此模型系统为 l 。b s 应用提供后台数j ：i j ：处理。 1 3 论文组织结构 本论文的组织结构如下： 第一章介绍了论文i i 9 i 7 1 究背景、研究内容_ ：f 【l 研究环境。 第二章分析3 s 应用的特点并洋细分析了现有的i b s 数据处理机制，指出其 存在的缺点，并提出了一种建议的实现方式。 第三章对本文提出的实现方式的基础一数据流系统的理论、模型、查咖语言 以及其他课题做一介绍。 第四章内容是阐述对现有的数据流系统进行空间操作的扩展，需要研究的课 题，并提出空问数据流系统模型，讨论此模型系统的实现。 第五章设计基于空l i l j 数据流系统的l 。1 3 s 应用数据处理实验，并列此系统实现 i 。b s 应用的数据处理进行性能分析。 第六章总结了整个论文并展望了今后的研究工作。 第一二章l b sj 衄川il i j 分忻 第二章l b s 应用的分析 2i l b s 应用概述及对其实现的分析 “i 随着宽带移动网络时代的即将到米，各种备样的应用不断地出现在人们的 7 l i a r , - i = | = l 。i b s 就足这佯种应用。这币ir 应用通过睹如( 申s 等定位技术获得移动 终端的地理位涵：信息，然后将这些位置信息提i 给侈动运营商、服务提供商或者 第三方使其能够基于位置信息向用户提供丰寓多彩的应用。 211 l b s 应用概述 u 搭应用通过定缸技术获得用户的位置信息目日i 比较常用的定位技术有两 大类，一类是是基于卫星系统的，主要是g p s 定位技术，另外一类是基于蜂窝网 络特定参数的三角定位技术，这一类的定位技术有艰于时问参数的到达时例差 ( | l m ed i f l e r e n c eo fa 1 1 r i v a l ，1 、d o a ) 、 至0 达时m j ( t i m eo fa r r i v a ，1 o a ) 等，基于方位角的到达j ；f 】度( d if e c t i o r lo fe l rr iv a i ，d o a ) 以及基于其他的参数 的c e 卜jd 、f in g 。r p t l i nl 1 jj 等。通过定位技术获得f l j 位置信息i 。b s 能够让用户或 者改备寻找或定位其他川，。、发备、交通： 具和资源，也能够让用户跟踪自己的 “足迹”。在这个过程中，l b s 应用对位置信息的清求可能来自于客户自己，也 可能来自于其他的实体，睹如服务提供商和网络。无论是来自于那一种方式的， 对于系统来蜕，客户的位置信息总是以一种流式的形式，源源不断地出现。 l b s 应用主要有两个动作： i 获得某个用户的位置： 2 利用获得的位置信息，提供一定的服务。 有了这两个动作就可以【亘】答移动用二的常见的4 个问题，这4 个问题构成 了l b s 的基础： w h e r ea mi ? w h e r ejst h en e a r e s t ? w h e r ei sm y ，? a n dh o wd o _ | g e tt h e r e ? 挂本上，当用户在特定的地点时，u 3 s 能够自动的被触发，这个特定的地点 可能是属于某个计费区域的。另外，客户自己为了特定信息的需求，也可以启动 l | 3 s 应用，这种例子包括找人或查询交通状况。 1 ) l b s 应用举例 常见的l b s 应用有查询当前位置或者与位置有关的信息，比如天气，的服 务，与位置有关的广告服务，导航服务，与位置有关的计费服务，财产管理服务， j 心嚣盯关的紧急j j | 务。t ij 咀分成以r 几类： 公兆发伞服务 服务提d i 尚提供此类m 川的+ 芒1 公众安仓的考虑此类服务一股利 政腑f | ：j 拙制婴求有犬。荚幽f 跌邦通信周要求的i ：9 li 服务就魁属- t i 此类另外还 柯：什紧急：队态通告服务1 1 移动用j 。处于某种紧急通告n 0 地理区域以内时，向 用户发出紧急：状态的通告，比圳聪风或火i 山喷发等紧急信息。 2 基于位置n 0i - t 赞服务 这种服务允f = = | 1 户能够依据自己的位黼或区域进行计费。基于用户的位蹬 信扈。可以生成不同的费率。不f 司的费率可能基于不同的活动区域，比如用户的 社区昶j 社区以外有不同的赞率，还可能基于时问。 3 v r a c k in g 服务 这一类的服务包括则产管理服务和交通监测服务，具体的例子有物流公司 的管理者需要知道雇员的位置利? 状态，父母想要知道自己孩子的活动，以及动物 f r 踪和其他财物跟踪等。另外还有一种可以：测高速公路上的拥塞或流量状态， 以便决定用户交通： 具的移动速度的服务。 d 基于位置信息服务 这类服务使用户能够访问和他位簧有关的信扈、，这些信息事先根据用户的 位置做过过滤或“裁剪”，这一类的_ f = | 1 户有可能是用户主动发起的，也可能是满 足一定的触发条件后，自动启动的，可能是单个的晴求结果或多个请求结果。这 一类的服务有导向服务、城市观光、依赖位置的广播服务和移动黄页服务。 2 ) l b s 应用的分类 从发起l 。1 3 s 应用的角度出发，可以将l b s 应用分为p u l l 型和p u s h 型 2 1o p u l l 型的应用是山客户向l b s 服务提供者请求位罱信息，以及与位置有关的l b s 服务， 比如典型的请求自己的当前位置的服务。p u s h 型的应用则不然，它是由服务提 供者发起的，对满足一定条件的客户提供一定信息的l b s 服务，比如与位置有关 的广告服务、基于位置的公路计费服务，基于位置的天气服务，以及移动伙伴列 表服务( m o b i eb u d d yl is t ) 等。 2 1 2 对实现l b s 应用的分析 i 。b s 应用通过定位技术获得移动对象的位置信息，图2 1 是一个通用的l b s 系统实现框架，从其中我们可以看出，位置获得系统位置负责获得移动终端的位 置信息，然后它将移动对象的位置信息发送到数据处理模块，数据处理模块根据 服务的要求刘位置数据进行处理，比如查询处理。在位置获得系统向数据处理模 块发送位置信息的过程中，要想得到移动对象精确的位置状态，就需要不断的从 第一章l b sj 、训帅1 分昕 俺t 划是得系统i 删x 1 多z 巩! 1 f 象的m 黼信息僻剖的缸w ? i 犬态越精确获取的位销 竹鬯越多血肴2 数_ l i ：i 卫新it t ：j 师i ：红j 沈越快。1 ；i h l u , t ij i l l 移j 力对象的缸谲2 信，自、足f ；l | 教到达率f k i 铈的敬w 流返1 i - 的f 、_ 错，2 数川流流入数处耻模块会刘其提汁5 很高 的数j ：l ! ：处理要求。 数据流 控制流 【纠2 11 b s 系统实现框架 从上一节我们知道，i i 强应用可以分成p u 】l 型和p u s h 型，针对这两类不同 类型1 1 9 应用，有不同的实现方式，下面就对此做出分析。p u i 型的i b s 应削， 其实现方式比较简单，可以简述主动清求位置信息的过程。此类应用仅需移动终 端或者第三方向系统发出位置信，自、请求，系统响应请求，向移动终端或第三方发 回位置信息即可。这一类的应用的实现比较直接，现有的基于传统数据库的技术 已经能很好的实现此类应用。但是对于p u s h 型的l b s 应用，其需要通过监测移 动列象的位置信息，并对满足一定条件的移动对象做出某种响应，有的应用还需 要做出及时的响应，比如公共安全应用，这里的条件一般是与移动对象的空间信 息有关的。显然，p u s h 型的应用是一种更加智能的应用，也是一种相对p u l l 型 l b s 应用来说，实现比较复杂的应用，因此，本文主要基于此类应用进行讨论。 我们这里介绍两种应用，作为迸一步讨论的基础，一种是基于位置的广告 服务。这利t 应用的一般的形式是通过获得用户的位置信息，当用户进入到一个特 定的区域时，一般是以一个商场为中一c 、f i _ | 一定范冈的区域，向用户发送相关的广 告信息。另外一种具有娱乐性的应用是移动伙伴列表服务。这种应用实时的跟踪 用户的位置信息，当两个川j 户距离接近时，这两个用户就会分别出现另一个用户 的伙伴列表中，然后基于每个用户的伙伴列表，可以开展一些娱乐项目。这两种 应j = | j 都是属于p u s h 型的应用。本文基于上述例子，对l b s 应用的实现进行分析 平【j 发计。 从数据处理方面，我们可以看到，p u s h 型的l b s 应用，需要对位置信息数 捌进行实i i 门处j _ | ! 。“这些数据进入数据库寸，数据库系统需要提“i 一种能够实 川处删这利一数州r 1 j | ：j l 制和fn1 钌会介绍常见n 1 头现i jl ；l i , j 。纠外- - , e 足这 “# 数卅和j 粜b 务- r 的数捌l j j 址r 孙l j 数拊比如j | 。r 的他胃拨，加。+ 告的区域等。 剥j 数捌i * 竖空叫i ! l j 处胖眦制，因此l b s 需要空m 数据处理”t i l i t 支持。 我”1 靠7 1p u s h 掣i l ：j r j 、i 1 确女下特。t 氧： i 数据更新频率快： 2 数据需要实时处理： ：j 与空问数据和操f i ：= f - - i 关。 从上而提到f n 两个例子干以上对p u s h 型l b s 应用的分析，可知p u s h 型3 s 应用首先是“t 某种服务删! 发的，触发i _ | 勺原因是满足这种服务的预先发定的某种条 件，服务触发以后，进入与这种服务相关的服务处理流狸。 p u s h 型l b s 应用的触发条件可以是多种多样的，例如，对于基于位置的广 告服务，触发条件是：当某用户的伙f l , - 进入某商场周匪l 一定的范围内。那么，这 种应川就要对位置数据库的位筒更新进行j 髓测，一旦发现某个位置更新满足上面 的触发条件，就会渊用这个删务相关的特定的处删。又比如伙伴列表服务，它的 触发条件就是两个用户f i ；j e e 离达到某一发定值的范围之内，当距离靠近，马上 启动棚应的服务处理。随着刁j 断有新的p u s h 型应用出现，触发条件会越来越多 佯。 2 2 常见的实现方式 本节就数据处理方式，划常见的l b s 应用的实现机制进行讨论。对于p u s h 型的u 搭应用，常见的实现方式有两种，一种是周期性的查询，一科，使用触发器 实现i 。另外，移动对象数据库也被用来对l b s 应用中移动对象的管理进行支持， 本节也对其做一介绍。 2 2 1 周期性的查询 首先假没有关系数据库或空问数据库保存了移动对象的当前位置信息，基 于这样的后台数据库，周册肚的查嘲的实现很简单，实现的一般步骤是，预设一 些针对这些应用的查询，并且周期性的调用这些查询，当查询得到结果时，调用 与这些结果相关的服务处理过程。 列于基于空间数据库的，i = | = | 于翻司数据的复杂性和多维性，般要借助空 问索引来提高空间查询的性能。比较常用的索引有r 树，以及由r 树发展而来的 其他索引。那么在这样的环境下，对于p u s h 型的应用，比如基于位置的广告业 第一章l b s 成j i j 的分忻 并：附发告i _ | 0 k 域怍为惫咖窗| - = | 周j j j 性：执行窗ii 赶咖获得处在广告区域 l j f # 到肼j 象。m 另引一种心川移动他韵。w i l l l l l l 或1 ) ise 。o 查i | j | _ ! | j 川。 2 22 基于触发器的实现 触发器，也被称作e v c 舰! j ! l j ( e v e n t c o n d il i o i l a cl l o n1 1 u e s ，e v c ) ，被 j 1 1 来舱训0 数据库畔，的事f q 和条f ：l 并且当探测到特定情况时，自动处理动作。一 个i f 细的剥触发器的处理过程的描述如下： 1 当数据库中声i 蝈的事件发生时，触发器被激活事件可以是对某个特定 关系n j i t t i 入、删除和更新。 2 当触发器被事p i ：激活时，不是立即执行，而是首先由触发器测试触发条 件。如果条f l 。不成立，则响应陔事件的触发器不做任何事情。 ： 蜘i 果触发器的条件满足，则与该触发器棚连的动作由i ) b v l s 执行。 利用数据库的触发器机制，可以实现列l b s 应用的处理，我们把l b s 应用 巾需要满足的条件当作触发器中的条件，如空旺i j 距离小于特定值，满足条件后需 要执行的任务当作触发器中动作，这样就可以实现l b s 应用。 文献1 9 i 中，提到用两种空 j 触发器，一种单移动对象触发器( s i r a p em o v in g o h j e tlt r i g g e r ，s i m 0 1 ) ，一种是双移动刘象触发器( b i n a r yn l o v i n go b j e c t 1 i - i g g e r ，1 3 i m o t ) 分别用来处理2 1 1 节提到的两个例子。它的实现方式可以 概括为：首先维护一个移动对织当前位置的数据库，当用户位置数据更新时，触 发带有空问渭词的窗口查咖，在s i m o n 中，由系统生成的r 树索引来提高查询的 效率，但是在b 州o t 中，由于两个对象都在运动，空间查询的区域也在运动，用 i 树索引会引起过多的节点分隔羽i 合并，所以这种这种触发器不能使用r 树的索 引，只有直接扫描数据表来实现查洵。 2 2 3 移动对象数据库 移动对缘数据( n o v in go b j e c td a t a b a s e ，n o d ) 是刘移动对象进行管理的数 据库，移动对象数据库的研究涉及存储和连续不断的处理在很多应用中( 包括 l b s ) 出现的移动对象。移动对象数据库不仅管理移动对象的当前位置，而且也 要管理移动对象的历史位置，以便进一步的使用。移动对象数据库的挑战在于支 持动态的，连续刁i 断的数据更新和移动的查询。移动对象数据库也是一种时空数 据库，因此其管理着带有空间和时间维的数据。为了提高查淘性能，需要引入对 移动对象的索引机制。因此在移动对象数据库上的时空查询处理的研究是一个非 常重要的研究课题。 蛾近 ：i i t 字盘咖处删上的研究：卜要集中于存储和索引寸，数据的能力 1 7 i 阶心这种商劲念州。l 膨川n 0j ；l ：j 苑( 即数更新i 火) 大多数n 0 研究集 。pj ：触世喙e 发索0 1 以艇支持频繁的史新。返止j 索q 0 洌j 二包括修改的删恪结构 修改的l 倒，以及修改的川剥和i 纠等。爆管这些索引比他统的刘应索引，能 f ! | 芗更好的支持数据更新世移动刘象和查i j | 一高到达率，无| 5 【；! i r , j 数j | ：, ；j - z ；j ；i g uh t 空 数据流匍5 没有被这些 1 _ - - 1 索引涉及，而s 应用j f 是这种类型的应用，所以研究 【b s 应用这种商动态的数据更新n 0 应用的数掘处理机制是很有! 【圣要的。 文献i = i 采用移动划象数= f , ! 1 1 4 v ；l 3 s 应用产生的位置流进行管理，其使用 触发器对p u s h 型s 应用产生的位置数抓；流进行管理，可以悦仍然采用得是传 统数据库的处4 1 1 j l 肯0 ，没有针对上面提到的i b s 应用特有的高数据到达率进行优 化。 22 4 上述实现方式的不足 以上的这些实现方式，都是基于传统的关系数据库。主要存在以一f ；f 足： l 以上的这些实现方式，有的不能做到实时处理。实时处理在p u s h 型i b s 应用中是基本的要求，尤其是剥于某些紧急服务，有特别高的实时在线处理请求， 川此列于以上的某些处理机制，显然是不能满足需求的。 2 由于s 这种应月j ，数掘更新频率较高，属于一种高动态的数据应用环 境，因；i j x t 于传统的，以处理持久数据为特征的数据库来说，数据库中数据的更 新频率过高，存活期很“短暂”，如果没有针对这种高动态的数据进行优化的话， 容易引起系统性能下降，所以上述实现方式在某些方面不能适合l b s 应用。 23 建议的实现方式 最近出现了一种专门处理数据集中应用的流数据库【8 】，即数据流系统，其的 显著特点是支持以数据流为输入的连续查内处理，数据以数据流的形式进入系 统，查咖处理是连续查询，不同于传统数据库的在数据集上操作的一次查询，连 续的奄洵可以做到对数据流的实时处理，在些需要实时处理的场合，这是非常 重要的。从上砸的分析，我们可知i b s 应用是一种以高速的位置流为特点的应用， 并且某些l b s 应用需要对位置数据流做实时的处理，因此，引入流数据库系统对 l b s 应用的数据处理进行支持，就是一件很自然的事情。 l 。b s 是一种需要空间操作支持的应用，然而，当前对数据流连续查询处理的 研究主要集中于对进入系统的数掘流，提供针对大量的连续查洵的在线处理能 力，剥于象l b s 这类应用需要支持的有空问和时间属性的数据流和查询却鲜有涉 第一章l b s 成川的分 j ； 歧。此需要州m 数捌流系纬：- ；l 入! i 孙，j 操怍进行叭究以使其能够支持i 峤 内川n 0 数拼：处川j 。本文i r 址州【lh 米题进行研究。 24 本章小结 升i 章剥l b s 应，| = 1 j 做简r b j 7 r 绍， 种常见的实现i b s 应刖的数据处理方式 爿：分析了l b s 应嗣的特，- 氧，接着介绍j l 最后分析了这些现有n j l 。b s 数据处理机 制的不足，并列l l j s 应用的数据处理机制提出用支持空l i j 操作n j 数据流系统来实 现的建议。 第二章数据流系统 第三章数据流系统 山十传统的数据库管理系统存处理连续流数据上的不足，因此最近一种专门 刷来处l _ ! 连续流数掘的数据流系统引起了人们的重视。l b s 这种数据更新怏，有 实时处删需求的应| 可以借助数据流系统的连续查询来实现数据处删。构建数据 流系统涉及 r 多方丽，首先我们需要抽象出数据流系统的数据模型，接着构建在 此数掘模型上的查咖，本章正足基于此顺序介绍数据流系统的。 3 1 数据流模型 就像关系数据库需要有数掘模型一关系一样j ，数掘流系统也需要有 自己的数据模型，那就是数据流模型3 1 。在介绍数据流模型之前，我们先引 入数据流| 1 勺概念。 3 1 1 数据流 数据流是一个实时的、连续的、潜在无界的、有序的( 隐含的通过到达时间 或者明确的时州戳) 项的序列3 i 。 因特网、w e b 以及传感器i 硐络等已经促使应用将数据看作一种连续的数据 流，而不是固定的数据集合。电话记录，股票报价以及从传感器那里得出的数据 都是数= | ：i ! ：流的例子。由此可见，数据流是连续的、无限的、快速的、随时间变化 的数据项的序列。在我们的i ，b s 应用中，位黉! 测算网络将移动对象的位置信息以 一种t 数掘流的形式输入数据库。这种数据流有以上介绍的数据流的一切特征。 与传统的数据相比，数据流具有许多自己的特点：它是大量的连续的无限的 数据；数据变化很快，并且要求快速【! | j 时的响应；数据流能很好地满足我们今日 数掘处理的需要；数据流管理中的随机存驭采用的是一种代价昂贵的单一线性的 扫描算法：仅仅存储到目前为止的现有数据；大多数数据流初始时处于相当低层 次或者多维状态，需要多层次化和多维化处理。 3 12 数据流模型 实时的数据流是一个以某种顺序到达的数据项的序列，可能只会被访问 次。既然数据项可能是高速到达的，那么数据流就可以采用元组链表的模型。单 第。j 章擞 橱流系统 个数抓j61 】能是个关系i 目1 【! = l 丌能是一个列象实例。m 于天系| _ i ：j 膜型一| = l ， 数_ i l l ：j m ! “i ，；f i * 存虚拟) t - 系| l i ；j l l 舜l l ：jj 0 7 1 l 。荫 j i ；- i 剥象的馍型t h 数据源；f | i 数撕项 ，瑶的址。j 州h 天联的数州类驯的膜型i ”j 。水文采f f 1 俐吐j 。引二天系的漠，钽。 1 7 l 数川流膜型中 此或，并所有输入数据的操作部魁建立在一个或多个进续 到达f | ! j 数捌流的基础上，r f i - l ：足z l 坝盘或者内i 午上。数执：流神i 传统的存储关系有 以一阿i _ j 不i 司： 数据流中的元素是暇机到达的。 系统不能控制数据元素到达的顺序。 数据流是潜在无限的。 一旦数据流的一个元素被处理之后，就会被丢弃或者存档：除非明确地 把数据存储在内存中，否则很难再次被检索，1 - i l l x j - - - 7 二数掘流的大小来说， 内存是相对较小的。 数据流模型上的操作剥琢l b 包括存储在传统关系一i ：i ! l o 数据。通常，数据流查 洵是在数据流和存储的关系数据上进行的。 3 1 3 数据流常见应用 下面介绍一些数据流i i 9 , 1 _ l 关应用，以便于了解数据流管理系统应该支持的查 咖。 1 传感器网络 传感器网络可以用在圳有复杂过滤和对异常情况进行响应的不同的监测应 用中。在多数据源上分析数据需要在多个流上进行聚集和连接操作。如果将l b s 应用中的能够自己获得位两：的移动终端看作传感裕网络中的传感器的话，那么 1 b s 中位置获得系统也可以看作个传感器网络。 2 网络流量临控 在计算流量统计和发现紧急状况( 比如，拥塞和拒绝服务) 的应用中已经使 用即席系统来进行近似实时的i n t e r n e t 流量分折。i n l t e r n e t 的流量模式被认为 遵从幂律分布，也就是既网络的大部分宽带资源是被一小部分的用户所占用，所 以监测流行的资源和终端地址是特别重要的。 3 金融报价器 联机的分析股票价格包括发现相关信息，确定趋势和套利的机会以及预测未 来的走势。 4 交易同志分析 联机地挖掘w e b 日志、通话记录和自动取款机等都符合数据流的模型。其目 的是发现消费者有趣的行为模式，识别可能具有欺准和可疑的消费行为并预测未 筇i 章数据流系统 32 数据流查徇 连续数捌流| ( ：j 查i i j 跟心统数据库管理系统一0 查瑚有很多共阮t 量。然而， 。g - 们之m j 存在- 4 、特有n j 区别：一次查咖平连续查i , f i j i ” 。一次查【 i j ( 一类包 含传统i ) b m s 的查m ) 是实施在数据集快照上的查询，结果返回给用户。而连续 查【f ! j 是在数据流连续到达的过程中进行连续求拘。连续查询的结果是随时叫产 生的，通常反映的是到目前为i l 的流数据。连续查【 j 结果可能被存储或随新数据 的到达进行更新，或者作为数据流产：生。表3 1 对一次查i _ f ! j 和连续查询进行比较。 表3l 一：布向和连续有淘的比较 泌 输入输m运行时间查询结果 一次查洵数据集数据集 一次运行查洵结果固定 连续查询数枷；流数据流或数据氏时间运行查询结果随时 隹 间改变 数据流馍型上的查洵处理有它独特n 勺难题i ”i h6 1 。下面，我们讨论这些难题 e t i , u l 个最主要的方而，并给出解决它们的儿个可选方法。 3 2 1 无界的内存需求 既然数据流的大小是潜在无限的，那么计算一个准确的数据流查询的结果所 需的内存数量也是无限增长的。数据集处理的外存算法比内存算法研究的多，因 为外存算法不能有效地支持连续查咖，所以它不适于数据流的应用，另外它的实 时响应时问通常比较慢。连续数据流模型适合那些对实时响应要求比较高，并且 速率随时i u j 高速变化、数据量产生比较大的应用。新数据是连续到达的，甚至在 旧数据还没有处理完，它就达到了；每个元素的处理时间要尽可能的短，否则计 算的执行时i f l j ；t 哿会很高，这样系统的处理就不能跟数据流同步。 a r a s u 等在应用有限的内存空间得- ：i 7 , 17 f t ；确的结果和利用磁盘i 方问得到近似结 果之间的区别上做了初步的研究。他们主要考虑那些具有潜在无限的内存需求 ( 跟输入数据流的大小是成比例的) 的有限查询。其研究结果表明：在不知道输 入数据流大小的情况下，对于诸如连接的大多数普通查询，除非查询所涉及的属 性的域有限，否则是不可能在内存中分配一个有限空间的。一个基本的直觉知识 第二章数“ 流系统 就j t 没“域n 0 限制i x l 为它们盯可能j ：暂来到达的数 ：【；：进仃连接操怍所以! i z , 须 1 ，j ! 端呃限数髓的幅一阽雠。 3 22 近似结果 矿如前面所说的，当局限于有限的内存删并不是总能j 、。：生准确的查询结果， 然而，收代准确结果的高质量的近似结果也是可以接受的。定义在数据流上的近 似算法的难题近年来在算法界的研究已经富有成效，这项：i ：作导致了一些为了数 掘简化和大纲构造的一些概括的技术，包括：草图( s k e t - c h e s ) ，随机取样( r a n d o 1 s a m p in g ) ，柱状图( is t o g f a l l s ) ，和小波( w a v e l e t s ) 。根据这些概括技术， 我们已经看到在近似查咖结果方面所做的一些：i ：作。例如近来的工作除了基于柱 状图的技术来进行数据流上棚关关系的聚集查咖的近似结果外，g i b e r t 等还提 出了个在数据流上建立小空问概要的通用技术，以提供很多类聚集查询的近似 结果。下面的2 个小：扎将介绍几个近似的方法，其中有些是数据流计算所特 有的。 3 2 3 滑动窗口 一种产生数掘流查咖的近似结果的技术就是j j l 过滑动窗i ：i ( s l i d i n gw i n d o w ) 在最近数据而不是在整个历史数据上进行查咖评估。例如，仅用最近一个星期的 数据来产生查询结果，这个星期以前的数据将会被丢弃。 在数据流上实施滑动窗e l 是近似的个很i i ：1 然的方法。它是定义良好且容易 理解的，更重要的是，它着重于最近的数据，在大多数现实应用中，相对于历史 数据，最近数据更加重要：如果一个人想实时地搞清楚网络流量模式，或电话记 录或交易记录，或科学传感数掘，那么观察最近数据比观察陈旧的历史数据更具 有参考价值。事实上，很多类似的应用中，滑动窗口并不是作为由于计算整个历 史数掘的不可行性而引入的一利，近似的技术，而是用户查询的一种查询语义。图 1 3 1 定义了一个窗口大小为7 的滑动窗e l 。 971 0 l575 宽度：7 ，。 、 剀31 滑动窗e 第二章数捌流系统 艇如l l | 十数撕流上应用滑动窗li 的l l , j 题l - 匝存在f r 多有待于研究的川翘。l 先个基术的问题就是 i 阿存数据流卜j t 义时n j j 戳以