移动对象索引 ST-tree.pdf

《移动对象索引 ST-tree.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、华南师范大学学报（自然科学版）2014年5月JOURNALOFSOUTHCHINANORMALUNIVERSITY第46卷第3期May2014（NATURALSCIENCEEDITION）Vol.46No.3文章编号：1000-5463（2014）03-0044-05移动对象索引ST-tree*叶小平，陈瑞鑫，周旋珍，陈鹏（华南师范大学计算机学院，广州510631）摘要：研究了一种基于时空”对称”和”统一”处理的索引模式ST-tree.首先，根据路网移动对象特征，以空间间隔和时间期间组成的时空矩形为技术处理单元

2、，讨论了一般区间元素集合上基于下右优先遍历序列的结构关系；其次，将时空矩形数据集合映射为空间间隔集合和时间期间集合，应用区间结构关系建立了路网移动对象数据集合数据结构；另外，由此研究了基于历史信息的移动对象索引ST-tree，它具有“一次一集合”的数据操作模式；最后，采用常规用例数据设计了基本仿真，通过与现有基本工作比较评估表明了ST-tree的可行性与有效性.关键词：区间集合数据结构；下右优先遍历；移动对象数据索引；数据查询模式中图分类号：TP311.13文献标志码：Adoi：10.6054/j.jscnun

3、.2014.04.008ST-tree：AnIndexforMovingObjectsYeXiaoping*，ChenRuixin，ZhouXuanzhen，ChenPeng（SchoolofComputerScience，SouthChinaNormalUniversity，Guangzhou510631，China）Abstract：Anovelindexmethodwhichdealswiththefactorsof“time”and“space”equallyanduniformlyispro-pose

4、d.Firstly，itregardsthetemporal-spatialrectangleasthebasictechnicalunitwhichconsistsofspatialintervalandtemporalperiodandstudiesthestructuralrelationshipforthesetcomposedoftheintervalelements.Secondly，itmapsthesetofspatial-temporalrectangleintothesetsofinterv

5、alsandperiodsrespectivelyandthedatastructureonthemareconstructedbythedown-rightfirsttraversing.Thirdly，itputsforwardtheindexschema，denotedasST-tree，todealwiththehistoricalinformationofmovingobjectsdataandcompletesqueryingwiththemoduleof“onetime，oneset”.Inadd

6、ition，simulationsarecarriedoutwhichcompareST-treewithsomecorrespondingex-istingworksandresultsindicatethefeasibilityandefficiencyofST-index.Keywords：structureofintervalset；down-rightfirsttraversing；indexofmovingobjects；moduleofquerying［1］随着计算机网络技术和无线定位通信设备迅速

7、如Jensen等提出BX树采用空间划分和数据转换发展，移动对象数据管理已成为时空数据库的研究来索引移动对象位置并得到较好的更新性能；Chen［2］＋热点并形成移动对象数据库（MOD）的专门领域.在等提出ST2B-tree基于B树，能够有效自动调优MOD中，移动点对象数据具有时空变化双重属性，结构索引.由于移动对象数据应用十分广泛，Pfos-［3］数据结构复杂，具有海量存储数据规模，数据索引er将其分为3类应用场景：①非限制性移动；②限成为MOD基本技术手段之一.移动对象索引需要制性移动；③交通网络移动.现实中大

8、多数移动对象同时索引时空信息并管理不同的时态状况，如索引往往被限制在路网（roadnetwork）当中，此时使用路历史轨迹、当前及未来位置数据.移动对象数据海量网中线性参考位置表示移动对象相应位置可达到良［4］规模需基于外存存储，现有历史信息索引多是基于好的降维效果.FNR树是一种典型的路网移动对B树及其扩展系列以充分利用B树高效更新特征，象索引，它使用一棵2DR树索引路网中线路，并对