一种改进基于交通网络移动对象索引方法.pdf

《一种改进基于交通网络移动对象索引方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第#+卷第,期重庆邮电学院学报（自然科学版）-./0#+"%.0,1!!2年3月4.5)67/.89:.6;<=6;>6=?*)@=AB.8C.@A@76D(*/*E.FF56=E7A=.6（@%7A5)7/GE=*6E*）H5;01!!2文章编号：!""#$%&’#（(""%）"#$"#)*$"#++一种改进的基于交通网络的移动对象索引方法!胡大权，邹永贵（重庆邮电学院，重庆#"""&%）摘+要：通过对基于交通网络（简称网络）移动对象索引方法,-.$/011的分析，提出了一种改进的/-.$/011方法。该方法充分利用网络信息，增大空间索引粒度，使用更合理的时间间隔，加强对轨迹

2、的索引。性能分析说明了/-.$/011方法较大程度地减少数据存储量和索引尺寸，提高了插入性能，并能有效地进行轨迹索引。关键词：索引；空时数据库；移动对象；交通网络；树中图分类号：/2*!!3!(；4#’%++文献标识码：5!"引"言随着无线通信技术、定位技术以及集成电路技［!］术的发展和民用化，基于位置的服务（678）日渐显露出美好的前景，并突显出潜在的巨大商业价值。无论是车辆监控、供应链管理、数字战场、移动电子商务等实际应用，还是战场仿真、网络游戏等虚拟环境都需要时空数据库系统（8/97:8）对大量移动对象的时空数据进行实时存储和快速检索，而索引则图!+交通网络扮演着重要的角

3、色。,BE3!/0JKKBLC1IM?0N近几年，人们对时空索引做了大量的研究，针对［(］的时间间隔（IBH1BCI10OJ@）。不同的情况提出了许多索引方法，如*9.$/011，［*］［#］［%］由于存储在(9.$/011中的空间对象是组成网/7$/011，;.$/011，:<*.$/011，/2.$［&，=］络的线段，其叶结点数据项（PCI0A）形如（6BD，/011等。绝大多数索引方法都假设移动对象在:77，Q0B1CIJIB?C），其中6BD为线段标识，:77为线空间中做自由运动，存储并索引移动对象每一抽样段的最小外接框（HBCBHRHS?RCDBCES?T），Q0B1

4、CIJ$时刻的时空信息。然而，现实生活中大量的运动都IB?C表示线段的方向，每个叶结点还有一个指向!9受到一定的外界限制，如高山、湖泊、公路、铁路、河.$/011的指针。(9.$/011的内部结点的数据项形流等，这些限制因素决定了移动对象只能按某种状如>I0，:77，其中>I0是指向子结点的指针，:77为态运动，通常是固定不变的，是事先已知的。如何利覆盖>I0所指的子结点的最小外接框。用已知限制条件，降低数据冗余度和存储量，简化索!9.$/011的叶结点的数据项形如（:BD，6BD，引方法，提高索引效率是我们的研究目标。我们主要关注基于二维交通网络点状移动对象的索引。#1CI0

5、JCL1，#1TBI，9B01LIB?C），其中:BD为移动对象标识，交通网络由结点和边组成，(个相连结点之间6BD为线段标识，#1CI0JCL1和#1TBI分别表示移动对象进入和离开线段时刻，9B01LIB?C表示运动方向。每当移的多线（>?@A@BC1）称作边（1DE1），多线由一系列的点动对象离开一条线段时执行,-.$/011的插入算法，!!，!(，!*，⋯表示，相邻(点!"F!和!"的连线称为线段（@BC1G1EH1CI）。如图!所示，移动对象只能沿着即以线段的起止坐标（$GIJ0I，$1CD，%GIJ0I，%1CD）为参数在(9.$/011查找包含线段的叶结点；再以运

6、动的边运动，经过结点再到另一条边。时间间隔（#1CI0JCL1，#1TBI）为参数，附带:BD，6BD，9B01L$#"移动对象索引方法$%&’()**IB?C等信息，插入到所找到的(9.$/011叶结点对应的!9.$/011中。考虑到时间单调递增的特点，新［)］［’］,-.$/011是一种基于.$/011的混合索引数据项只是简单地插入到!9.$/011最近（最右）的结构，是用一棵二维（(9）.$/011以线段为粒度索引叶结点，而不是用.$/011的插入算法，这样可以提相对固定的网络。(9.$/011的每个叶结点对应一高存储空间利用率。棵一维（!9）.$/011，索引移动对象对

7、应线段上运动当以时空窗口（*9间隔）为参数执行范围查找!收稿日期：(""#$!"$!#++修订日期：(""%$"#$"!作者简介：胡大权（!’=#$），男，重庆垫江人，讲师，在职研究生，研究方向：UV8，时空数据库，P$HJB@：WRDXYW?IHJB@3L?H。·"·.......重庆邮电学院学报（自然科学版）...............第*J卷时分!步：!先在"#$%&’((中用$%&’((的查找算［)］!"改进的移动索引方法#$%&#’((法查找空间查询窗口所包含的线段和叶结点；"在