（计算机应用技术专业论文）面向智能交通系统的移动对象索引技术研究.pdf

河海大学硕十研究生论文 面向智能交通系统的移动对象索弓【技术研究 摘要 随着城市交通网络上各种传感器技术的快速发展，人们可以自动地采集并保 留路网上大量移动对象产生的交通数据流信息。管理和分析数据流，并从中获得 有用信息及随时间演化规律以支持交通控制成为智能交通系统研究的核心问题。 交通数据流具有实时性、连续性、无法预知性、大小无界性、一遍扫描性等 特点。在智能交通系统中，除了对特定车辆的监控外，更加关注时间维和空间维 上车辆聚集信息的获取。因此，如何对海量的流数据进行组织和索引，以达到快 速有效检索和分析的目的，就成为信息时代人们迫切需要解决的问题。 论文引入数据流在线微聚类与离线聚类分析相融合的方法对数据流进行处 理。其中，本文设计了一种滑动窗口模型下为数据流提供在线中间处理的微聚类 算法：m c s t r e 锄，实现了在线数据压缩；而离线状态下，根据在线存储的微聚 类时空分布变化，分析数据流的演化过程，从而实现对数据流的时段划分。在此 基础上，提出种适应于管理交通流数据历史聚集信息的时空索引结构 h d c t r e c ，将数据流的时间和空间分布特征分开管理，以支持用户在线状态下对 过去任意时间段内的聚集查询请求和离线状态下的聚类分析以及分时段演化分 析。实验表明本文设计的数据流在线、离线处理方法以及索引结构具有良好的可 操作性，为智能交通系统的设计与实现提供了强有力的支撑。 关键字：数据流、数据流在线微聚类、快照、时空索引技术、聚集查 询 河海大学硕上研究生论文面向智能交通系统的移动对象索引技术研究 a b s t r a c t r e c e n t l y w i mt h ed e v e l o p m e n to fw i r e l e s sc o m m u l l i c a t i o n ，g 一p o s i t i o n i n g 锄d s e n s o rt e c l l i l o l o 百酷，d a t as 仃e 锄sh a v eb e c o m eu b i q u i t o l l sb e c a u s eo fs u c hl a r g e n u 劬e ro fa p p l i c a t i o n sw 恤c hg e l l e r a t eh u g ev o l u m e so fd a t ai n 锄硼t o m a t e dw a y t h ec o r ei s s u co fi n t e l l i g e n th a n s p o r t a t i o ns y s t e m ( i t s ) i sh o wt 0m a n a g ea i l d a n a l y z et l l ed a t as t r e 锄st og e ta v a i l a b l ei n f o m a t i o na n dm ee v o l v e m e n to fd a t a s 仃e a mw i t l lt i m e o n eo fm o s ti m p o r t a n tp u 印o s e so fi t si sm a c r os c h e d u l i n gf o r 仃a n s p o n a t i o n ， w l l i c hi sm o r ec o n c e m c d粕u ts p 撕o t 锄p o r a l a g 伊e g a t e i n f o m a t i o nt h 觚 m o n i t o 订n go fs p e c i f i cv 幽c l e s c o n s i d e r i n gm eo n 一1 i n e ，u n p r e d i c t a ：b l e ，c o n t i 肌o u s ， o n e p a s sa n dl a 玛ev o l u m e so f 仃a 伍cd a t as t i e a m s ，i ti su r g e n tt oo 唱a i l i z ea i l di n d e x t l l eh u g ev o l u m e so ft r a f f i cd a t at 0r e a l i z eq u 耐e sf a s ti nn l o d e mt i m e s i nt h i sp a p e r ，w ew i l la i l a l y z em ep r o b l e mo fs p a t i o - t e i t l p o r a la g g r e g a t i o n so v e rd a t a s 仃e 锄sf o c u s i n go nm eh i s t 嘶c a ld a t ab yc o m b i n i n gm i c r o c l u s t 甜n go n l i n e 、】l ，i m e v o l u 廿o na i l a l y s i so v e rd a t as h e 锄o f f 二l i n e b a s e do n l ei n t r o j e c t i r l 岛w ew i l l p i o p o s ean e ws p a t i o - t e m p o m li n d e x i r 坞m e m o dh d c t r e e ，w h i c hc 锄s u p p o nb o m a n yu s e r - s p e c i f i e dt i m ew i n d o wq u 秭e sa 1 1 de v o l u t i o na n a l y s i so v e rd a t as t r e a m s o m l i n e t l l ee x p 谢m e n ts h o w st h a ti ti sh a i l d a b l ef o rt h em a n a g e m e n to ft r a m cd a t a s t r e 锄sa n dm ei n d e x i n gm e t h o dw h i c hc a j lb eu s e dt oa n a l y z ea i l dm i n et h et 1 1 l t ho f m ee v o l u t i o no fd a t as t r e 锄sf o ri t s k e y w o r d s ：d a t as t r e a m s ，o n k n e 血c m - c l u s t e r i n go v e rd a t as t r e a m s ，s n a p s h o t s ， s p a t i o _ t b m p o r a ii n d e x i n gm e t h o d ，a g g r e g a t eq u e r y i i 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 狐曙年 厂月fv 日 ( 注：手写亲笔签名) 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论文作者( 签名) ：丞枷略年月f - 日 ( 注：手写亲笔签名) 河海大学硕士研究生论文 面向智能交通系统的移动对象索引技术研究 第一章绪论 城市交通需求的不断增长，对城市交通基础设施、交通规划技术以及交通管 理手段提出了更高的要求。以智能交通系统( i n t e l l i g e l l tt r a i l s p o r ts y s t e m s ，i t s ) 为平台的智能化研究已成为交通规划和管理者研究的主要课题，并且在一些城市 已有了具体应用。 自上世纪8 0 年代术起，i t s 在世界范围内的应用为交通系统的有效运行起到 了积极作用。同时，i t s 对城市交通系统的影响也使得城市交通规划理论和方法 产生了相应变化。从某种意义上讲，i t s 可理解为是从技术上缓解交通需求、增 加交通供应、充分挖掘现有交通供应设施潜力的一种手段和方法，其“智能化 体现在以下三个方面： ( 1 ) 车辆依靠自身的智能在道路上安全自由地行驶，在陌生地方不致迷失方 向。 ( 2 ) 道路依靠自身的智能将交通流调整至最佳状态，提供及时准确的行车路 线，缩短行车时间，减少阻塞。 ( 3 ) 交通控制管理中心依靠系统的智能对道路和车辆的状态进行实时监控， 及时处理事故，保障道路畅通。 为了满足以上三个方面的需求，可以看出i t s 的关键在于交通信息的采集和 应用。近年来，随着计算机网络、电信和传感器技术的日益发展，使得由这些应 用领域中自动产生的一种新型数据一一数据流也变得无处不在。这些数据流可以 是关系元组、网络性能参数、传感器读入值等呓。1 ，它们以大量的、连续的、随 时间变化的、无法预测的、无限制的流的形式到达。传统的人工调查方法以及以 感应线圈为代表的交通检测方法依然是当前交通信息获取的主要手段。这些传统 的方法由于人为的因素或是其他因素，得到的数据往往具有较大的误差和偏差。 同时，由于数据处理周期的原因，已不能满足i t s 对交通数据的需求。如何使用 高效的在线概要信息来处理数据流成为目前国际数据库研究领域的一个热点。 然而在线的聚集查询只能粗略判断特定条件下交通状态，对数据流历史数据 潜在的时空规律特征分析就无能为力了。研究人员花费高昂的代价保存大量的历 史信息，当然并不是仅仅为了满足用户任意时间段的聚集查询，更是为了实现数 据流潜在的规律信息挖掘，为i t s 的设计提供决策支持。因此，本文引入了数据 流在线处理与离线分析相融合的思想，以在线聚集信息计算为前提，对数据流进 行离线状态下的聚类分析，为数据流按时问划分提供了理论依据。 河海大学硕上研究生论文面向智能交通系统的移动对象索引技术研究 1 1 研究背景 随着移动通信技术的发展和车载、手持设备的普及，越来越多的应用提供“基 于位置的服务”( 1 0 c a t i o n - b a l s e ds e r v i c e ) ，这都为i t s 提供动态交通信息服务创造了 条件。动态交通信息服务系统一般由采集、处理和发布三部分组成。其中，交通 信息采集主要通过人工采集或自动采集，自动采集技术又分为如下两种：固定型 如感应线圈、视频采集等；移动型主要为浮动车技术。 浮动车技术作为一种新兴的交通信息采集方式，通过g p s 技术跟踪车辆的 瞬时位置、速度和时间，然后通过车速处理分析系统获得路网车速等准确实时的 动态交通信息。该技术具有成本低、效率高、实时性强和覆盖范围大的特点，已 成为目前国际上系统中采集道路交通信息的重要技术手段之一。 通过城市交通网络日益先进的各种硬件技术，人们每天都可以自动地采集并 保留路网上大量移动对象时刻产生的数以千万计的交通信息。这种以流的形式到 达的数据被形象地称为数据流。典型的数据流包括无线传感器网络应用环境中， 由传感器传回的各种监测数据、网络监测系统与车载g p s 道路交通监测系统的监 测数据等，本文中研究的数据流即车载g p s 装备的浮动车移动对象产生的数据 流。 移动对象随时间产生的信息具有信息量大、难以准确描述的特点，使人们很 难从海量的移动对象信息中迅速准确地找到自己所需的信息，从而形成了大海捞 针的局面。因此，如何对海量的流数据信息进行组织和索引，以达到快速有效检 索和分析的目的，就成为了信息时代人们迫切需要解决的问题。 以交通宏观调度为主要目的的智能交通系统，除了对特定车辆的监控外，更 加关注移动对象产生的聚集信息的获取，如特定时间段、特定区域内的交通流量、 行车平均速度等信息。聚集查询( a g g r e g a t i o nq u e r y ) 也是数据库管理系统中的一类 重要查询，在移动对象数据库中，它扮演着重要的角色。和普通的对于对象的个 体查询相比，这类查询对于数据分析和决策支持更为有用。例如在交通分析系统 中，个别车辆的位置和速度并无太大用处，而某段时间、某个区域的车辆的总量 和平均速度却是判断道路交通畅通或拥堵状况的重要信息。与普通关系数据库中 的聚集查询不同，移动对象上的聚集查询条件可能包括时间( t e m p o r a l ) 、空间 ( s p a t i a l ) 、或者时空( s p a t i o t e m p o r a l ) 谓词。如上面提到的交通分析的例子，用户 需要分析某个空间区域( 例如某个路段或路口) 、某段时间( 上下班交通高峰时 段) 的车辆的平均速度( 均值是一个聚集函数) ，该要求可以写成如下聚集查询： s e l e c tv d a y a v g ( v v o l i c i t y ) f r o mv e h i c l e i s t o r yvm a pm 查询平均速度 根据车辆历史信息和地图进行查询 河海大学硕士研究生论文 面向智能交通系统的移动对象索引技术研究 w h e r ev p o s i t i o ni nm 啪g e 在给定地域范围内查询 a n dm a r e 铲“中心公园给定地域查询范围为中心公园 舢l d v t i m ei n 【1 7 ：o o ，1 8 ：0 0 】 查询1 7 ：o o 一1 8 ：0 0 时段 g m u pb y v d a y查询每日平均速度 由于数据流的应用领域越来越广泛，面向数据流的聚集查询研究引起了人们 的极大兴趣。这种以流的形式到来的数据不同于存储在磁盘上的传统关系数据， 而是以快速、无限、连续的流的形式存在。它可以被视为无限多重集合，集合中 每个元素具有形式 ，其中s 是一个元组，t 为标识s 的时间戳，t 的取值可以是 s 进入数据流系统的时问或者数据源产生s 的时间。 由于内存资源有限，数据流系统只能通过在存储器中开辟滑动窗口来保存近 期到达的数据流数据，以实时地支持查询请求。随着数据流源源不断地流入滑动 窗口，必然有部分旧数据从滑动窗口中流出，这罩称流出滑动窗口的数据为历史 数据。目前，数据流管理技术的研究工作主要集中在分析处理近期数据流数据上， 而忽略了对数据流历史数据的分析处理与存储管理。在实际应用中，存储器的容 量是有限的，而源源不断到达的数据流是无限的，因此存储器中只能存储一段时 间内的数据流数据，以实时地支持查询要求。然而，当查询请求所涉及到的数据 查询范围超出了存储器中存储的数据，或者查询请求需要直接访问历史数据时， 已有的数据流查询技术就无能为力了。 由上面的例子可以看出，研究对数据流历史数据的查询需求是普遍存在的， 如研究人员需要查洵历史日志信息以跟踪了解某些特定范围内的交通信息，为智 能交通系统的设计提供决策支持。这类对数据流历史聚集信息的查询请求同时也 给智能交通系统的管理及维护提出了问题：系统要从海量数据流中获得哪些有用 信息? 如何存储和检索这些信息? 如何利用它们才能使存储数目如此巨大的历 史数据具有现实意义? 其中，对于存储和检索的问题，采用传统关系数据库存放移动对象位置信息 固然可行，但其不能支持区域查找功能。像查询指定区域过去某一时段或者某一 时刻移动对象的分布情况，传统数据库管理方法无能为力，只能采用时空数据特 有的管理方法才能实现对移动对象的查询及分析。事实上，对移动对象的查询和 分析处理，无论是面向单个移动对象的请求还是面向聚集信息的请求，其实现技 术都植根于基于移动对象数据库的时空数据的索引与查询。因而，构建一种时空 索引结构，在这样的背景下高效管理随时间变化的海量时空数据信息成为移动对 象数据和数据流研究中的新问题。 对数据流历史聚集信息的任意时段的查询，是为了通过查询所得的结果对空 间区域内的交通情况做出初步判断。如利用区域内查询不同时段移动对象的总量 河海人学硕i ：研究生论文面向智能交通系统的移动对象索引技术研究 或平均速度判断区域内交通的拥堵情况，从大量历史数据的查询中获得该区域交 通分布规律，从而进行更现实的应用。例如研究人员可以利用观察到的规律对交 通设施做适当调整，以缓解或避免区域内的拥堵情况。 同时，移动对象上的聚集查询处理不仅可以被用来响应用户的查询请求，也 是时空数据挖掘的重要技术。例如，频繁模式挖掘( 行e q u e n t p a t t e mm i n i n g ) 的实 质是计算具有较大聚集函数c o u n t 值的属性组合；而聚类分析( c l u s t e r i n g ) 与分类器 构造( c l a s s i f i c a t i o n ) 过程中，大量的统计分布计算可以转化为聚集查询结果的代数 计算。因此，本文对数据流历史数据存储的用意并不仅仅在于满足用户一定误差 范围内时空数据的查询需求，同时也希望，花费昂贵的代价保存的大量历史数据 能够有更高层的应用：可以比较准确地反映出数据流随时间的推移在不同空间区 域内发生的变化，满足用户需要的任意时间段内数据流的挖掘请求，以得到数据 流的时空关联特性。这种时空关联特性对帮助发现重要的数据流演化特性，挖掘 出有用信息形成规律都提供了很大的方便。 1 2 研究目的及意义 交通流量根据时间的不同呈明显的变化趋势，本文通过对宁波市装载g p s 的机动车辆采集到的原始数据进行分析和处理，随机抽取了路段标号为2 2 、1 7 8 6 和3 1 4 9 的三条路段，分别代表市区、中环和郊区，如图1 1 所示。对这三条路 段在2 0 0 7 年5 月1 5 同( 星期二) 一天机动车的分时段车辆流量( 车辆j 、时) 进行 统计，得到了宁波市三条不同路段上不同时段机动车流量图，如图1 2 所示。 。i 图1 1 宁波市部分路网 4 ，一黪 河海人学硕上研究生论文面向智能交通系统的移动对象索引技术研究 从图1 2 来看，交通流的分布随时间有着较大的差异，有趋于平稳状态的时 段，也有处于上升、下降趋势的时段。应该看到，城市不同区域内交通流流量随 时间的分布不尽相同，但仍然有各自明显的变化规律。因此，有必要区分不同区 域内不同时段的交通分布情况，进行分析归纳，才能获得有用的信息。 1 6 0 0 1 2 0 0 筵8 0 0 d o o 0 图1 2 宁波市三条路段机动车流量值 掌握交通流量分时段的变化规律在生活中很有现实意义，用户可以通过分时 段的查询获得当前时间或者将来某个时间段的交通通行情况，选择方便的时段和 路径出发前往目的地，从而避免由于交通拥堵带来的时间上的等待和资源的浪 费，同时也减轻了交通压力，节约了资源，为智能交通系统的设计提供了支持。 另外，数据流随时间的推进源源不断地到来，历史数据也急剧增长，人们不 可能采用相同的粒度管理概要信息：统一的细粒度将会给存储空间带来极大压 力；统一的粗粒度将会降低查询结果的精确度。对研究人员来说，选取恰当的粒 度和合适的结构存储移动对象数据流的历史数据也具有非常重要的现实意义，也 是面向海量数据研究不可避免的问题。需要设计合适的时间粒度模型和数据存储 结构，实现对数据流的压缩，在存储压力与计算精度之间到达一种平衡。 从数据结构方面来说，对数据流历史数据的存储，大多数的应用只是将所有 移动对象的位置和位置变化信息直接写入到数据库或者数据仓库中，如大型的移 动对象数据库( m o v i n go b j e c t sd a t a b a s e ) 。但这种存储往往以磁盘或者磁带为存储 介质，通常要花费计以g b 量级的空间需求。并且，通常对移动对象数据库中的 海量历史数据进行时空聚集查询时，一种查询处理方法是查询所有符合时间、空 间条件的移动对象，然后再进行聚集查询。因而查询操作需要大量的i o 交换， 效率低下，显然不能适应实时系统的需求，这就需要设计适应聚集查询的数据存 储结构。 从应用的层面上讲，一方面，对于海量数据流历史数据的存储是有必要的， 而存储设备的限制，迫使研究人员尽可能地对数据进行压缩，需要采用较粗的粒 度归纳数据，以减少存储带来的压力并且维持较高的查询效率；另一方面，人们 河海大学硕十研究生论文 面向智能交通系统的移动对象索引技术研究 对历史数据查询请求的目的当然是希望返回的结果能够有助于现实应用，要求查 询结果的误差在允许的范围内，这就希望存储的粒度尽量细，对数据的归纳尽量 完整。由此可知，解决移动对象数据流历史数据存储空间的无限需求与查询效率 及精度需求之间的矛盾，关键往往在于科学的粒度模式的设计，这也成为现阶段 对于历史数据研究关注的一个热点。 以往的工作中，研究人员通常采用多粒度的时间存储模式，认为近期数据的 利用价值高于历史久远的数据，提出对历史久远的数据采取粗粒度( 如以年为单 位) 的聚集值存储方式，对于相对较近的数据采取细粒度( 如以分钟为单位) 的聚集 值存储方式。可以看出，多时间粒度的存储方式在一定程度上缓解了存储容量、 存储精度及查询跨度三者之问的矛盾。但是，这些方法明显存在着一些问题： ( 1 ) 粗粒度存储丢弃了大量原始的历史数据，不能支持分组聚集查询和基于 任意时间段的聚集查询； ( 2 ) 根据时间“远“近 来划分粒度的方法掩盖了数据流原有的周期性规律， 使研究人员对数据流演化分析的需求愈加难以实现； ( 3 ) 数据一经粗粒度聚集就不可能再次细分，从而不能支持历史数据按不同 时间段的划分。 因此，按照这种简单的模式对时间进行多粒度划分不能支持时空流数据分时 段规律的发现。然而，聚集信息的计算为数据流上的在线数据挖掘提供了有力的 支持，同时，数据挖掘技术也给数据流的离线聚类分析乃至演化分析拓展了思路， 正是建立在微聚类基础上的数据流的演化分析为不同区域根据规律进行时问段 划分提供了重要依据。 离线的聚类分析是种寻求数据自然聚集结构的重要方法，对于分析海量数 据有非常重要的意义。聚类是概念描述和偏差分析的先决条件，它的重要性体现 在：聚类是一种处理大量的、繁杂的、属性众多且没有类标志数据的有效方法， 在知识发现的过程中，聚类经常被作为其它数据挖掘任务的前奏。利用聚类把整 个数据集合分成子类之后，其它数据挖掘工具就更容易在聚类结果的基础上发现 有用的规则和模式。例如，如果从移动对象产生的数据流全体数据中得不到明显 的模式，可以先对数据进行聚类，再从每个聚类中发现规则和模式。如可以利用 大聚类找到一些数据密集区域，在此基础上，再具体分析得到形成密集的原因， 为交通疏导提供了有力的帮助。 基于上述几个方面问题的描述，本文试图通过引入可控的查询误差，提供数 据流近似处理，提出一种新的适应于交通流数据历史聚集信息的时空索引结构 h d c t r e e ，支持用户在线状态下对过去任意时间段内的聚集查询请求。同时，考 虑到需要为用户提供离线状态下的数据流聚类及演化分析的要求。本文引入数据 6 河海大学顾上研究生论文 面向智能交通系统的移动对象索引技术研究 流在线微聚类与离线聚类分析相融合的方法【4 】对数据流进行处理：在线状态下， 算法增量地维护一定数目的微聚类( m i c r o c l u s t e r s ) 单元，并以特定的初始时间粒 度存储微聚类快照( s n 印s h o t s ) ；离线状态下，算法进一步利用了在线存储的微聚 类快照，提取特定区域内两个给定时刻的快照，根据两个时刻的微聚类分布变化 分析数据流在该区域的演化过程，为对该区域数据流进行时段划分提供了依据。 本文将在后面的章节给出时空索引树h d c 仃e e 的结构描述以及其相关应用 操作，包括在线的聚集查询和离线的数据流分时段演化分析。最后通过试验证明 这种索引结构的精确性与优越性，并利用聚类特征向量对数据流的时空关联特性 进行分析。本文希望在理论分析和实践检验的基础上，开发一套有效的移动对象 聚集查询和数据流分析处理技术，为基于位置的服务提供有力的技术支持，为智 能交通系统的设计与维护提供理论和现实依据。 1 3 本文主要工作 综上所述，本文在详细分析数据流相关特性的基础上，设计了在线微聚类处 理与离线聚类分析相结合的数据流处理模型。在有限的内存空间内，设计了一种 有效的时空索引结构：h d c t r e e ，对空间区域内移动对象数据流历史数据进行概 要存储及索引，不仅在线的满足了用户移动对象任意历史时间段内的聚集查询， 同时为用户在离线状态下对数据流进行分时段地演化分析提供了技术支持。 为了满足用户对其感兴趣区域的在线查询和离线的分析。本文设计了基于微 聚类快照的复合式索引结构：h d c 一仃e e 。首先采用空间索引技术，如r t r e e ，对 空间区域进行划分，形成较小的子区域，然后对每个区域的概要数据利用附加树 索引结构a d d t r e e 进行分时段概要存储。 考虑到数据流模型的重要特点之一：单遍扫描( o n ep a s s ) ，处理过的数据不能 再次还原。所以仅对数据流历史数据进行简单地概要存储并不能满足用户离线状 态下对数据流分时段演化分析的需求，这就使得该技术为智能交通系统的实现所 做的贡献大大降低。为了弥补简单概要数据计算在现实应用中的不足，本文在数 据流滑动窗口子模型下设计了一种移动对象数据流在线聚类算法：m c s t r e 锄算 法，形成微聚类快照。 索引结构还维护了在外存中存储相应时间戳的微聚类快照，利用微聚类“快 照”对移动对象产生的数据流空间概要信息进行压缩存储，并在离线状态下通过 不同时间戳微聚类快照的比对，分析数据流在用户指定区域内随时间变化的演化 过程，以此作为该区域时间段划分的依据。 本文的主要贡献在于将本文将对交通数据流的处理分为在线和离线两种状 态，在此基础上所设计的时空索引结构也具有了在线查询处理和离线演化分析的 7 河海大学硕士研究生论文面向智能交通系统的移动对象索引技术研究 功能。不仅满足了用户对数据流历史信息的在线聚集查询请求，同时实现了用户 在离线状态下对交通流分布的分时段演化分析。这两种功能提高了数据流的查询 性能，拓展了数据流的查询功能，为分析特定时段特定区域内的交通状况提供了 技术支持，在交通流数据分析和决策支持方面具有广泛的应用前景与实践意义。 1 4 章节安排 本文的余下部分组织如下： 第二章主要介绍数据流历史数据的存储，包括数据流的特点、数据流模型以 及模型上的聚集查询；根据数据流的相关特性，以b a t r e e 、a h r b t r e e 为例简要 介绍目前常见的数据流时空聚集计算索引技术并对其进行分析；最后简要介绍现 有的几种数据流聚类算法。 第三章设计了滑动窗口模型下的移动对象数据流在线微聚类技术： m c s t r e 锄算法，并且提出一种新的基于数据流微聚类快照的时空索引结构： h d c - t r e e 。 第四章给出新的时空索引的应用，包括时空聚集查询、离线的聚类方法及数 据流的分时段演化分析。 第五章给出实验结果及评价。就索引占用空间大小、时空查询条件对查询效 率的影响及聚类分析的质量等问题进行计算，并就结果进行具体分析。 第六章总结与展望。 河海大学硕上研究生论文面向智能交通系统的移动对象索引技术研究 第二章相关研究 本章着重介绍数据流的相关研究，包括数据流的管理、面向数据流的聚集查 询及数据流历史数据的存储技术，由此解释了现有的数据流历史数据存储模型存 在的问题及其难以实现的功能。并以h t a 模型和a h r b t r e e 为例讨论了数据流聚 集计算的索引技术。最后结合数据流的在线聚类算法简单介绍了其在线、离线处 理相融合的思想，为时空索引与数据流处理相融合找到了很好的切入点。 2 1 数据流相关研究 近年来，随着信息处理在工业生产、经济信息处理等领域的广泛应用，数据 已不仅仅拘泥于文件、数据库等传统的静态形式，一种连续、无界、不定速的流 式数据( 即数据流) 已经出现在越来越多的应用领域。目前，对数据流相关技术 的研究已经成为数据库领域又一新的研究热点。 2 1 1 数据流的分析与管理 数据流不同于存储在磁盘上的传统关系数据，而是以快速、无限、连续的流 的形式存在。典型的数据流包括无线传感器网络应用环境中由传感器传回的各种 监测数据、股票交易所的股票价格信息数据、网络监测系统与道路交通监测系统 的监测数据、电信部门的通话记录数据以及w 如上的数据等。管理和处理数据 流的系统称为数据流系统。数据流可以被视为无限多重集合，集合中每个元素具 有形式 ，其中s 是一个元组，t 为标识s 的时间戳，t 的取值可以是s 进入 数据流系统的时间或者数据源产生s 的时间。 区别于传统应用模型，流数据模型具有以下几个特点： ( 1 ) 数据流中的数据元素在线到达，即实时性； ( 2 ) 数据流中的数据元素连续不断地到达，即连续性； ( 3 ) 系统无法控制将要处理的新到达的数据元素的顺序等，即无法预知性； ( 4 ) 数据流的潜在大小是无界的，即大小无界性； ( 5 ) 数据流中的数据一旦流过，就被丢弃，不能再次被访问，即一遍扫描数 据； ( 6 ) 数据流中的查询是相对静止不变的，而数据是时刻变化的，即持续查询 性。 由数据流的特点可知：数据流的潜在大小是无界的，且数据元素在线到达。 9 河海大学硕 ：研究生论文面向智能交通系统的移动对象索引技术研究 如果利用传统技术处理这种模型，必须将数据全部存储到介质中，然后通过提交 d m l ( d a t am a n i p u l a t i o n1 a n g u a g e ) 语句访问存储介质来获取查询结果。传统数据 库存储的是静态关系型数据记录的集合，它们具有限定的大小、可控制的操作、 详细定义的结构，同时这些数据具有持久性。传统数据库中的计算具有时间复杂 度和空间复杂度，其查询处理为单次查询，查询计划为静态的，且最终生成确定 的查询结果。另外，传统数据库中的数据除非明确地加入了时间戳的属性，否则 没有时间的概念。 虽然这种模型也能充分地满足某些商业或个人的信息存储的要求，但许多当 前以及今后更多的应用要求数据管理系统能对不断快速变化的数据流提供在线 分析支持。由于数据流规模宏大且到达速度很快，要对数据流中的个体数据一一 进行处理，需要很大的空间消耗，而内存资源有限，传统技术难以满足实时要求， 所以那样的处理不切实际。而且，由于： ( 1 ) 在一些情况下，由于合法性或者隐私性，个体数据不能被保存； ( 2 ) 可得的个体数据可能不相关； ( 3 ) 个体数据高度易变，需要巨大的存储空间。 这样一来，对个体数据的精确信息进行处理就显得更不容易。事实上在很多 实际应用中，例如决策支持系统、查询优化等，用户并不需要获得确切值，而仅 需要一个近似值。而且聚集信息在长时间内稳定，仅需要较少的存储空间。比如 某路段上的车辆容量是几乎不变的，但是道路网上来来往往的车辆是时刻变化 的。可见，相比于车辆这一时刻变化的个体数据，车辆容量是很稳定的。因此， 设计单遍扫描算法( o n e - p a s sa l g o r i t h m ) ，实时地给出近似查询结果就成为数据流 模型下数据处理的目标。算法的关键在于设计一个远小于数据集规模的结构，从 而可以在内存中处理数据。相对于数据流的规模而言，这种名为概要数据结构 ( s y n o p s i sd a t as t m c t i j r e ) 的规模至多应该是次线性的，即如果流的长度为n ，则概 要数据结构大小不超过o ( 1 0 9 州) ) ，并且处理流上每一组数据的时问不超过 o ( 1 0 9 烈) ) 嘲。图2 1 显示了传统数据处理技术与数据流处理技术的差异。 d a l a b a 键o r 胁 砌e 1 1 0 1 1 s e ( a ) 传统数据处理模型 ( b ) 数据流处理模型 图2 1 传统数据处理模型和数据流处理模型的比较 从图2 1 可以看出，传统的数据处理技术将所有数据存放到数据库或者数据 1 0 河海大学硕士研究生论文面向智能交通系统的移动对象索引技术研究 仓库中；系统响应用户提交的d m l 语句，搜索数据存储媒介，返回查询结果。 当数据规模很大时，数据往往以磁盘或者磁带为介质，因而执行查询操作需要大 量的i ，o 交换，效率低下，不能适应实时系统的需求。相反，新的流数据处理技 术并不保存整个数据集，仅维护一个远小于其规模的概要数据结构，从而能够常 驻内存。流数据处理技术往往包含两部分算法，一部分监控流中的数据，更新概 要数据结构；另一部分响应用户查询请求，返回近似查询结果。举例来说，假设 研究人员想要获知某段时间内经过某一区域的移动对象平均速度。在传统方法下， 首先所有移动对象位置及其它相关信息被存放在外部介质中，然后进行分析，得 到最终查询结果。由于数据规模宏大，需要大量的i o 交换，可能需要很久才能 够得到结果为该区域：8 5 。而在数据流处理方法中，仅仅需要访问内存中的概要 数据结构，因而可能仅仅需要很短时间就能获得答案为该区域：8 5 5 o 。可以 看出，数据流处理方法比传统的处理方法要快很多。尽管该方法得到的结果并不 精确，但是往往并不影响用户的最终决策。 针对数据流的这些特点，设计一个良好的数据流管理系统( d s m s ) 用于管理 流式数据便成了研究人员关注的问题。目前很多大学和机构正在致力于开发一种 面向新的应用的数据流管理系统，比较成型的数据流管理系统原型有斯坦福大学 的s t r e a m 系统【7 】，布朗大学、布兰代斯大学和麻省理工大学联合开发的 a u r o r a 【8 】，美国加州大学伯克莱分校的t e l e g r a p h 项引9 ，1 0 】等。 数据流模型根据不同的时序范围可以划分成多种子模型，包括界标模型 ( 1 a n d m a r km o d e l ) 、滑动窗口模型( s l i d i n gw i n d o wm o d e l ) 和快照模型( s n a p s h o t m o d e l 。令n 表示当前时间戳，s ，e 分别是两个已知的时间戳。界标模型的查 询范围从某一个已知的初始时间点到当前时间点为止，即 a s ，a n ) 。滑动窗口 模型仅关心数据流中最新的w ( w 也称为滑动窗口大小) 个数据，其查询范围是 a 懈( n w + 1 o ) ，a n ，随着数据的不断到达，窗口中的数据也不断平移。快照模 型则将操作限制在两个预定义的时间戳之间，表示为 ，a e ) 。界标模型和滑 动窗口模型由于要不断处理新来的数据，更接近于真实应用，因而得到更加广泛 的研究。 2 1 2 数据流上的聚集查询 数据流上的聚集查询是数据库管理系统中一类重要的查询，与普通的个体查 询相比，这类查询对于数据分析和决策支持更为有用。它涉及多种聚集查询函数， 如c 0 删，s 啪，a v e r a g e ，m i n ，m a ) 【等等。本设计主要运用的是计数函数c o 僦， 以对区域内满足查询条件的车辆总数进行查询，用于分析交通状况。 在数据流上进行查询处理需要考虑的三个因素是： 河海大学硕士研究生论文面向智能交通系统的移动对象索引技术研究 ( 1 ) 查询算法需要的内存； ( 2 ) 查询处理需要的时问： ( 3 ) 返回查询结果的精确程度。 第一条约束了数据流处理算法的设计，因为在通常的数据流环境下，都只有 有限的内存资源可以用来运行查询处理算法，因此要求算法把数据流概括成概要 信息，但这是以精确性为代价的；第二条要求该算法能快速获得查询结果；第三 条要求能够保证近似计算结果在一定误差范围内。 在连续数据流上的聚集查询依据不同的数据流应用环境，对精确度的要求也 有所不同，具有不同的近似概率。 一般地，近似聚集查询方法主要有两类：在线联机查询处理和预计算提纲方 法。第一种方法由用户控制计算结果，在前面的计算结果的基础上，计算数据流 下一时刻的聚集结果，并对它进行改进；第二种方法需要在查询之前建立或存储 查询概要，当接到聚集查询时，由查询概要数据直接得出查询结果。第二种方法 需要对查询概要数据进行更新维护，这些工作都是基于预处理方法的。 在这种情况下，所设计的算法应能简要概括并预先存储数据流的概要数据， 并在适当的范围内保证查询概要数据的准确性。这些概要数据存储在一个有限的 空间内，能够用于对用户查询提供近似查询结果，并且能够保证近似查询结果在 一定的误差范围内。这种近似的联机查询结果特别适合大多数数据流处理的应用 环境，它们对数据流的查询都不是以提供一个精确的查询结果为目标，而是需要 系统为其提供一个有价值的聚集值。 流式数据本身的独特性给数据流计算模型中的查询处理带来了许多新的挑 战。如上所述，当局限于一定的内存空间时，对数据流的查询不可能总产生精确 的结果，所以高质量的近似结果在许多情况下也可以被接受。这就意味着需要在 准确性与存储数据流概要的存储空间之间进行平衡，同时还有一个附加的限制是 对每一个数据项的处理时间要尽量减少。最近几年对定义在数据流上的近似算法 的研究已经取得了许多重要的成果，主要有以下几种：滑动窗口技术】，随机抽 样技术，直方图技术【1 3 ，14 1 ，小波技术【15 1 ，s k e t c h 技术【1 6 ，17 1 。研究人员用概要信 息代替大量原始数据，这样一个小小的样本可以被认为包含了一个数据集的本质 特征。在d s m s 中它可能是一种最简单的概要形式，其他的概要可以通过一个 样本来建立。然而取样可能会产生一些误差，比如求最大值、求最小值等。如何 有效地对数据进行取样，以及如何减少误差，则成了进一步研究的课题。 目前数据流的研究成果主要集中在分析处理存储于内存中的最近一段时间 内的数据流数据，仅仅对数据流的最近的滑动窗口中的数据进行求值。人们关心 的往往是最新的数据，认为最近的数据要比旧的数据重要得多，查询也多关注当 河海大学硕上研究生论文面向智能交通系统的移动对象索引技术研究 前时间到过去h 长度范围内。例如仅仅考虑最近一周中的数据，而其他一周之前 的数据都不作考虑。这在现实世界的许多应用中具有一定的道理，但对于移动对 象产生的带有明显时空周期性变化规律的流数据来说，保存众多历史数据，更方 便从数据流的源头对数据流进行分析，从而挖掘出更深层次的规律。 2 1 3 数据流历史数据存储面临的挑战 由于内存资源有限，数据流系统只能通过在存储器中开辟滑动窗口来保存近 期到达的数据流数据，以实时地支持查询请求。随着数据流源源不断地流入滑动 窗口，必然有部分旧数据从滑动窗口中流出，称流出滑动窗口的数据为历史数据。 数据流管理技术已经成为一个热点研究问题。目前的研究工作主要集中在分 析处理近期数据流数据上，而忽略了对数据流历史数据的分析处理与存储管理 【l 犯。在实际应用中，存储器的容量是有限的，而源源不断到达的数据流是无限 的，因此存储器中只能存储一段时间内的数据流数据，以实时地支持查询请求。 然而，当查询请求所涉及到的数据查询范围超出了存储器中存储的数据，或者查 询请求需要直接访问历史数据时，已有的数据流查询技术就无能为力了。 然而对数据流历史数据的查询请求是普遍存在的。例如，交通维护人员需要 查询历史日志信息以跟踪了解交通流数据随时间和空间变化的规律，确保用户某 些个性化查询需求，如范围查询、最短路径查询、最近邻查询等。因此，数据流 的历史数据的存储与查询足一个值得研究、关注的问题。那么，是否可以用传统 d b m s 的关系表来存储管理这些数据流中的历史数据呢? 答案是否定的，原因 是： ( 1 ) 数据流具有无限的连续性随着时间的推移，数据流历史数据的容量可以 无限大，传统d b m s 难以存储管理如此之大容量的数据。 ( 2 ) 多数情况下，为满足实时性，只需得到一定误差范围内的近似结果即可 满足数据流系统中的查询请求，而传统的d b m s 很难支持任何近似查询操作。 ( 3 ) 对于一些聚集查询请求，传统的d b m s 需要扫描外存中的关系表数据来 得到查询结果，这个过程会产生许多i o 操作，不满足数据流系统中的实时查询 要求。 显然，传统的数据库技术和现有的硬件条件不能用于存储与分析持续快速增 长的数据流历史数据，这就需要研究与数据流特点相适应的数据流历史数据的管 理技术，同时也引出了一些难题： 面对大量移动对象随时间空间的转移而产生的数以千万计的交通信息，应该 遵循何种规律定时定量地保存交通流的历史数据? 即， ( 1 ) 应该以何种时间粒度统计存储这些源源不断到来的数据? 在这个循环存 河海大学硕上研究生论文面向智能交通系统的移动对象索引技术研究 储的过程中，如何在存储需求和对特殊时问跨度内的统计精度之间达到一种平 衡，从而保证在期望的近似程度内实现一个有效的替代? ( 2 ) 受限于一次扫描的特性，应该保存哪些概要信息才能保证周期性的概要 统计信息，在用户需要的时间跨度内能够提供时空聚类分析和观察交通流的分时 段演变过程? 关于数据流历史数据的研究目前并不是很多，时间存储模型也比较单一，基 本上是采用多时间粒度的存储方式，提出对历史久远的数据采取粗粒度( 如以年 为单位) 的聚集值存储方式，对于相对较近的数据采取细粒度( 如以分钟为单位) 的聚集值存储方式，如图2 2 所示。 。1 2 枷s 。3 id a 粥。2 4b 啪，q 锨 1 警ll j ! ui lill ju ! llil llll ji ! ill jluii - 刀坍e ( 囊) o w 3 l 妇2 4b 伽堪1 4q l r s 1 5m i n u 懈。 ulili ! lil lllllii ! lii lililui ll ：liill- 胁孵 ( b ) 舶渺 ：l 竺j 兰奎l ：置l 兰i 竺l 兰l ：l ：l 砌舯 ( c ) 黼 图2 2 常见的多时间粒度存储模型 常见的历史数据多时间粒度存储模型的时间表中包括自然时间表( 图2 2 ( a )