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

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

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

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

支持固定网络中频繁更新的移动对象混合索引模型

IMOFN是一种支持固定网络中频繁更新的移动对象混合索引模型,它由一棵描述固定道路网络的2D R*-Tree、一组对时间进行索引的1D R*-Tree和一个存储移动对象实时数据的Hash数组组成.IMOFN既管理了移动对象实时位置,支持位置的频繁更新;又保存了历史轨迹,提供了范围查询、拓扑查询以及轨迹查询等多种有效的实时和历史查询功能.通过实验与FNR-Tree和MON-Tree进行性能比较,证实了IMOFN模型高效的查询能力.     

基于动态距离的近邻查询算法研究

移动对象轨迹数据的挖掘是移动对象数据库的一个重要研究方向,从轨迹数据中得到的信息可以应用到交通控制、气候预测以及生态研究等多个方面.基于轨迹数据形式化定义时态距离,用相对简单的近似距离替代精确距离来减少查询过程中的计算量.在关系模型和树结构模型上,实现基于动态距离的距离查询、时间点最近邻查询和时间段最近邻查询算法并对查询效率加以比较.实验结果表明,树模型的查询效率明显高于关系模型.最后在树结构模型中引入嵌入式索引进一步提高了查询效率.     

受限网络移动对象的概率最近邻查询

基于自由空间移动对象概率最近邻查询,给出受限网络移动对象概率最近邻(CNPNN)查询概念,提出一种基于网络概率Voronoi图的CNPNN查询算法.利用基于网络距离的概率度量得到不确定数据的网络概率Voronoi单元,建立网络概率Voronoi 图覆盖受限网络.使用对点查询具有优势的R+树,对不确定数据的网络概率Voronoi单元进行索引,减少搜索时间.确定查询对象所在网络Voronoi单元,得到查询对象最可能的最近邻.实验结果表明,该算法时间复杂度为O(n2+mlogmn),在一定条件下具有较好的性能.     

MOQ-QR:基于QR-树的连续K近邻查询算法研究*

综合分析了R-树和四叉树在处理移动对象的连续K近邻（简称CKNN）查询算法中的不足,提出了一种基于R树和四叉树索引结构,去解决移动对象连续K近邻查询算法。该算法通过对移动对象分配静态空间,并在研究区域内利用QR-树和hash表作为索引去存储移动对象以此计算查询点与移动对象之间的空间距离。实验证明,该算法与现有算法相比,不仅提高了数据的查询效率,而且降低了系统资源的消耗。     

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

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

支持动态负载的移动对象最近邻查询算法

提出一种基于双层网格索引的移动对象KNN查询算法,解决由移动对象速度变化引起的动态负载问题。算法采用粗细双层网格将不同速度的移动对象分开索引,在粗网格中索引运动速度快的对象,在细网格中索引运动速度慢的对象,减小了网格索引的维护代价,提高了KNN查询效率。针对真实数据集实验结果表明,与传统算法相比,该算法能更有效地解决动态负载问题。     

一种基于城市交通网络的移动对象全时态索引

高效地管理移动对象以支持查询是一个重要课题.为了支持在城市交通网络上的移动对象过去、现在和将来位置查询,提出了一种新的索引技术.首先提出基于模拟预测的位置表示模型来改进对移动对象将来运动轨迹的预测精度;其次根据城市交通网的特征,设计了一种全新的动态结构自适应单元(AU),将其开发为一个基于R树的索引结构(current-Au);最后在AU的基础上进行扩展(past-AU)使其支持移动对象历史轨迹查询并且避免了大量的死空间.实验证明,AU索引优于传统的TPR树和TB树索引.     

基于LSTM的移动对象位置预测算法*

移动对象位置预测是基于位置服务的重要组成部分。现有的移动对象位置预测算法有基于马尔可夫链的算法、基于隐马尔可夫模型的算法、基于神经网络的算法等,然而这些算法都无法解决移动对象轨迹数据中位置过多带来的维数灾难问题。为了解决这一问题,提出了位置分布式表示模型(location distributed representation model,LDRM)。该模型将难以处理的表示位置的高维one-hot向量降维成包含移动对象运动模式的低维位置嵌入向量。随后,将该模型与基于长短期记忆网络(long short-term memory,LSTM)的位置预测算法结合为LDRM-LSTM移动对象位置预测算法。真实数据集上的实验表明,与现有算法相比LDRM-LSTM算法在预测准确性上有较大的提升。