一种基于固定网络的移动对象运动轨迹索引模型

实际应用中移动对象通常运动在城市固定道路上,针对此特征研究人员已提出一些相关索引模型,但都存在一定的局限性,表现为索引模型只管理对象的历史位置信息或实时位置信息以及只对窗口查询或轨迹查询进行优化.IMTFN是一种基于固定网络的移动对象运动轨迹索引模型,管理移动对象的实时位置信息和历史轨迹信息,并且有效优化窗口查询及轨迹查询操作.IMTFN由一个管理固定网络的2D R^＊-Tree、一组管理移动对象运动轨迹的1D R^＊-Tree以及记录移动对象实时位置信息的Hash结构组成.最后通过实验IMTFN分别与STR-Tree与FNR-Tree进行性能比较,证明IMTFN模型提供速度更快的查询操作.     

道路网中基于RRN-Tree的CKNN查询

现有针对基于道路网络的CKNN查询研究,主要是将道路网络以路段和节点的形式进行建模,转化成基于内存的有向/无向图,该模型存在2个问题:一个是道路网络中路段数据量大,导致索引结构分支过多、移动对象更新频繁;另一个是图表示方法不能很好地处理十字路口转向、U型转弯等交通规则。针对此问题,提出道路网中基于RRN-Tree的移动对象CKNN查询算法,包括索引结构设计和移动对象查询算法设计,采用路线对道路网建模,基于网络边扩展方式,实现复杂条件下的道路网络CKNN查询。实验结果表明,在各种网络密度和兴趣点对象分布密度下,与经典的IMA/GMA算法相比,基于RRN-Tree索引方法的查询性能提高1.5倍~2.13倍。     

基于位置服务的道路网数据模型综述

随着基于位置的服务(LBS)在交通管理服务中的广泛应用,获取并管理移动对象的位置信息成为必要,建立一种有效支持服务的道路网数据模型成为研究的重点和难点。道路网数据模型是对各种道路相关信息进行描述以支持移动对象位置信息获取及表示的数据模型。文中对国内外的道路网模型研究作了一个简要概述及分析。     

基于位置服务的道路网数据模型综述

随着基于位置的服务（LBS）在交通管理服务中的广泛应用，获取并管理移动对象的位置信息成为必要．建立一种有效支持服务的道路网数据模型成为研究的重点和难点。道路网数据模型是对各种道路相关信息进行描述以支持移动对象位置信息获取及表示的数据模型。文中对国内外的道路网模型研究怍了一个简要概述及分析。     

网络受限移动对象不确定性轨迹的索引

近年来,人们对于如何表示和处理移动对象的不确定性进行了研究,提出了一些较为有效的模型和算法.但是,在如何索引移动对象的不确定时空轨迹方面,相关的研究工作十分有限.为了解决上述问题,本文提出了一种网络受限移动对象不确定轨迹的索引结构(UTR-Tree),并给出了相关的索引更新及查询算法.在该索引结构的支持下,移动对象数据库不仅可以快速地处理对移动对象过去可能位置的查询,而且能够对其现在及将来的可能位置进行高效的查询处理.     

网络受限移动对象过去、现在及将来位置的索引

提出了一种适合于网络受限移动对象数据库的动态轨迹R树索引结构(network-constrained moving objects dynamic trajectory R-Tree,简称NDTR-Tree).NDTR-Tree不仅能够索引移动对象的整个历史轨迹,而且能够动态地索引和维护移动对象的当前及将来位置.为了比较相关索引结构及算法的性能,进行了详细的实验.实验结果表明,与现有的基于道路网络的移动对象索引方法如MON-Tree和FNR-Tree等相比,NDTR-Tree有效地提高了对网络受限移动对象动态全轨迹的查询处理性能.     

基于位置范围的道路网skyline查询

随着无线通信和定位技术的发展,道路网skyline查询在基于位置的服务等方面越来越重要。考虑到现今道路网中位置隐私保护和定位设备的精度问题,用户在道路网上的位置通常用一个范围来表示。但是,已有的道路网skyline研究都是基于单一查询点。针对这一问题,研究了一种新的查询——基于位置范围的道路网skyline查询(RNS),提出了一种基于边界点替换的有效查询处理算法。另外,针对已有的道路网skyline查询中复杂的道路网距离计算对查询效率的影响问题,通过计算兴趣点在道路网上的有效skyline路段,将其与道路网信息融合,建立了道路网skyline模型。基于该模型设计了一种能有效支持RNS查询的道路网skyline索引SSR-tree,提出了基于索引的RNS查询处理算法。通过大量实验验证了所提方法的有效性,并比较了基于索引的算法在查询效率和精度上的提高。     

面向路网的移动对象全时态高效索引模型

针对现有索引模型的冗余搜索问题,考虑路网拓扑结构及交叉口转向约束条件,提出一种面向路网的移动对象全时态高效索引模型。采用添加临近路段信息的方法索引历史轨迹和实时位置信息,设计新型窗口查询算法,实现移动对象查找,并运用指数平滑法进行轨迹的预测。实验结果表明,该模型具有较好的更新及查询性能。     

NU2RA:一种路网中不确定移动对象范围查询分析方法

目前移动对象的各类查询研究大多假设对象的位置确切可知,但实际上除了更新时刻外,其他时间对象的位置只是一个可能的范围.因而大多数基于确切位置的查询算法并不可行.而现有的涉及不确定性的查询方法大多仅针对自由移动的不确定查询或者不确定目标.针对道路网中查询和目标位置均不确定的情况,提出了一种NU2RA分析方法.根据查询范围对网络进行划分,用分布码表示目标的可能分布,得到不确定目标与不确定查询范围的22类拓扑关系,并且给出了目标在不确定查询范围内的概率计算方法.该方法不依赖于具体的不确定移动对象模型,对不确定历史轨迹和不确定的近期将来运动趋势同样适用.     

道路网络中移动对象的索引研究

为了能有效地实现网络中移动对象的过去、当前和将来轨迹的查询,提出了一种L2R索引,它由两层R树和一个链表结构组成。两层R树用以索引道路网络和移动对象过去的运动,对象当前的位置和将来的预测轨迹信息保存在链表中。L2R索引不仅可以支持网络中的移动对象的轨迹查询,尤其是可方便的在纵向链表中查询在同条路线上的所有对象。在此索引基础上文中实施了对移动对象的范围查询和点查询,最后通过实验表明L2R结构的索引和查询性能均要优越于TPR树。     

时空相点移动对象数据索引PM-Tree

随着移动定位技术和无线通讯技术发展,移动对象的应用领域越来越广阔.位置随时间而变化的移动对象产生的时空数据具有规模大、多维性、结构复杂和关系复杂等特点.由于移动对象的运动轨迹大多被限定在特定的交通网络中,因此基于路网的移动对象索引成为时空数据索引研究的一个重要应用分支.目前,针对移动对象历史数据的区域查询优化的研究重点...     

一种基于道路网络的移动目标数据库模型

移动目标数据库(moving object database)有别于一般数据库技术的重要特征之一就是不仅可以对移动目标在数据库记录的时刻进行位置查询,而且可以对不同记录时刻之间以及未来时刻的位置进行查询,其研究的首要问题是建立移动目标运动及位置更新模型.目前有大量依靠其他辅助设备(如GSM网络)定位的盲终端设备(如移动电话,PDA等),存在着MOD管理的潜在需求,需要对它们建立合适的运动及位置更新模型,来为移动用户提供基于位置的服务.针对这类无自定位能力的移动目标,利用它们通常运动在城市的道路网络上这一特点,提出了基于道路网络的移动目标历史和未来速度计算模型,在此基础上提出了基于道路网络的非等时位置更新模型.与传统的速度计算模型相比,基于道路网络的移动目标历史和未来速度计算模型在考虑移动目标定位误差时可以降低移动目标位置预测的误差;与等时位置更新模型相比,基于道路网络的非等时位置更新模型在平均预测误差相近的情况下,可以减少移动目标和定位设施之间的通信量.     

路网中速度不确定移动对象的k近邻查询

目前在基于道路网的移动对象的各类查询研究中,大多都是在假定移动对象速度固定不变的基础上进行的.而实际上因为外界环境和自身情况等不确定性因素的影响,对象的速度可能会发生变化.基于此,本文提出一种基于路网的速度不确定的移动对象的k近邻查询处理方法.在查询时刻根据查询点位置执行查询操作,得到构成查询点k近邻的候选对象集合,再根据概率计算方法得到结果集及其概率.实验结果表明本文所提方法是有效的.     

基于道路网络的移动对象聚类

现有的基于道路网络对象聚类算法eb-cls采用网络距离描述移动对象间的相似性,没有充分利用对象的时间和空间属性,造成算法不能体现移动对象动态演化的移动模式,频繁更新聚类结果并且聚类精度不理想,执行效率低等问题。针对这些不足,提出基于道路网络的移动对象聚类算法MOBORN（Moving Objects Based on Road Network）,该算法引入时空相似系数,考虑了移动对象速度、方向和位置。当移动对象间的时空相似系数达到给定阈值,将其分到同一聚类,并动态维护聚类结果,减少聚类次数。实验结果证明,与eb-cls算法相比,该算法聚类精度保持在97%以上,运行效率提高了40%。     

基于受限移动对象当前及将来时刻检索的时空索引结构研究

在给定的空间及时间范围内,如何构建高效的时空索引结构,以实现对移动对象快速有效的检索,是实现定位服务、智能交通、数字化战争等诸多应用中所迫切需要解决的问题.本文依据移动对象的运动特点,提出了一种面向当前及将来时刻快速更新及有效检索的索引结构—PQR树.PQR树是综合PMRQuad树和R*树的结构,首先依据道路分布用PMRQuad树将移动对象的索引空间实行粗略的层分割,将所有快速移动对象与道路相关联.然后用R*树索引分布在各个子空间块内的类静止对象.实验结果表明PQR树具有良好的更新和查询性能.     

基于道路分布的移动对象动态组合索引方法

交通管理信息服务中需要高效的索引方法来管理移动对象。针对这一需求,提出了一种基于道路分布的移动对象动态组合索引结构。在此结构的基础上,采用了自底向上的动态更新算法和路段连接方法,提高了移动对象的更新和访问效率。通过实验验证了该组合索引具有更优的更新和查询性能。     

时间依赖路网上的移动对象K近邻查询算法

随着基于位置服务的广泛应用,时间依赖路网上的对象查询逐渐成为研究热点。以往研究大多只针对时间依赖路网上的静态对象(如加油站、餐厅等),未考虑到移动对象(如出租车)的情况,而移动对象的查询在日常生活中有着非常广泛的应用场景。因此,文中提出了一种针对时间依赖路网上的移动对象K近邻查询算法TD-MOKNN,该算法分为预处理阶段和查询阶段。在预处理阶段,通过建立路网和网格索引,提出了一种新的移动对象到路网的映射方法,解除了以往研究假设移动对象恰好在路网顶点上的限制;在查询阶段,采用启发式搜索,借助倒排网格索引计算了一种新的高效启发值,通过预处理信息和启发值设计了高效K近邻查询算法,并给出了算法的正确性证明和时间复杂度分析。实验验证了所提算法的有效性,相比现有算法,TD-MOKNN算法在遍历顶点数和响应时间上分别减少了55.91%和54.57%,查询效率平均提升了55.2%。     

基于HBase的路网移动对象时空索引方法

在处理路网移动对象时,由于HBase只能采用key查询,不适用于移动对象的多维查询,导致HBase存在存储索引与查询效率不高的问题。针对此问题,在HBase存储结构的基础上设计并实现了一种高效的路网移动对象HBase索引框架（RM-HBase）。首先,对原生HBase索引框架的上层HMaster和下层HRegionServer进行改进,解决分布式集群数据的热点分布问题,提高空间数据的查询效率;其次,提出路网移动索引——RN-tree,解决空间划分中的"死空间"问题,同时提高空间中路段的查询效率;然后,基于上述对HBase的索引改进,分别设计了时空范围查询、时空K最近邻（KNN）查询和移动对象轨迹查询的查询算法;最后,实验选用了同样是基于HBase分布式数据库而提出的时空HBase索引（STEHIX）框架作为对比对象,分别从索引框架的性能和算法的查询效率两个方面对RM-HBase的性能进行分析。实验结果表明,所提的RM-HBase在数据的均衡分布性能和时空查询算法的查询性能方面都优于STEHIX框架,有助于提升海量路网移动对象数据的时空索引效率。