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

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

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

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

基于Buddy*-Hash的移动对象时空查询方法

索引技术可以提高数据检索和查询效率,为了实现对时空数据库中移动对象的查询操作,需要引入时空索引技术。在传统Buddy-树的基础上提出Buddy*-Hash索引结构,根据扩展查询窗口策略给出范围查询算法。实验结果表明,基于BH索引结构的范围查询算法具有良好性能。     

一种新的道路网络连续查询处理方法

基于道路网络的连续k近邻查询是移动对象数据库领域的研究重点和热点.提出了一种新的道路网络有向图模型,通过引入有向网络空间度量,利用基于内存的格网索引和线性链表结构来对移动对象当前位置和道路网络有向图模型进行存储和管理;基于有向距离度量提出了单向网络扩展(DNE)算法,以减少连续k近邻查询的网络扩展搜索代价.实验结果表明,DNE算法性能优于现有的连续k近邻查询处理算法.     

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

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

移动对象数据库中时空索引技术的研究

提出了基于移动对象运动轨迹的时空立方体模型,在该模型中,移动对象的运动轨迹按一定时间间隔划分,每段运动轨迹对应一个最小外接时空长方体,它是存储,访问的一个基本单位.基于该模型设计了相应的时空索引和时空查询算法.验证表明,模型在减少数据冗余和时空查询性能方面有较大提高.     

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

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

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

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

路网中移动对象轨迹索引的研究

索引结构对有效保存和查询移动对象的运动轨迹是至关重要的.根据交通网络中移动对象的轨迹特点,讨论了目前具有代表性的几种索引结构,重点分析了MON-Tree索引结构,将它与3D-Rtree进行了性能比较.在此基础上,提出并实现了一种基于MON-Tree的网络中移动对象轨迹数据库原型.     

移动对象时空方向关系建模

针对现有方向关系模型不能有效刻画移动对象方向关系变化的问题,提出了一种移动对象时空方向关系建模方法。通过对移动对象的时空方向关系进行分类,采用连续快照模型的思想,基于投影模型对移动点对象之间的时空方向关系进行建模,分别定义了静态时空方向关系模型、历史时空方向关系模型和时空方向关系演变模型。时空方向关系演变模型刻画了移动对象的动态时空方向特征,可以有效支持时空查询和时空推理等,对移动对象的时空特性研究具有重要的理论意义。     

基于公路网的移动对象数据库数据模型

移动对象数据库对大量移动对象的位置信息进行管理，能够支持传统数据库不能进行的时空查询，考虑到大多数移动对象的运动都固定在已知的路线中，基于公路网的移动对象数据模型、通过对公路网拓扑图的数字化转换，能够对移动对象进行有效的管理，该文采用实时平均法来反映每条线路的动态运行情况，对移动对象未来位置进行了精确预测。     

Modeling and querying moving objects in networks

Moving objects databases have become an important research issue in recent years. For modeling and querying moving objects, there exists a comprehensive framework of abstract data types to describe objects moving freely in the 2D plane, providing data types such as moving point or moving region. However, in many applications people or vehicles move along transportation networks. It makes a lot of sense to model the network explicitly and to describe movements relative to the network rather than unconstrained space, because then it is much easier to formulate in queries relationships between moving objects and the network. Moreover, such models can be better supported in indexing and query processing. In this paper, we extend the ADT approach by modeling networks explicitly and providing data types for static and moving network positions and regions. In a highway network, example entities corresponding to these data types are motels, construction areas, cars, and traffic jams. The network model is not too simplistic; it allows one to distinguish simple roads and divided highways and to describe the possible traversals of junctions precisely. The new types and operations are integrated seamlessly into the ADT framework to achieve a relatively simple, consistent and powerful overall model and query language for constrained and unconstrained movement.     

多视角融合的时空动态图卷积网络城市交通流量预测

城市交通流量预测是构建绿色低碳、安全高效的智能交通系统的重要组成部分.时空图神经网络由于具有强大的时空数据表征能力,被广泛应用于城市交通流量预测.当前时空图神经网络在城市交通流量预测中仍存在以下两方面局限性:1)直接构建静态路网拓扑图对城市空间相关性进行表示,忽略了节点的动态交通模式,难以表达节点流量之间的时序相似性,无法捕获路网节点之间在时序上的动态关联.2)只考虑路网节点的局部空间相关性,忽略节点的全局空间相关性,无法建模交通路网中局部区域和全局空间之间的依赖关系.为打破上述局限性,本文提出了一种多视角融合的时空动态图卷积模型用于预测交通流量.首先,从静态空间拓扑和动态流量模式视角出发,构建路网空间结构图和动态流量关联图,并使用动态图卷积学习节点在两种视角下的特征,全面捕获城市路网中多元的空间相关性.其次,从局部视角和全局视角出发,计算路网的全局表示,将全局特征与局部特征融合,增强路网节点特征的表现力,发掘城市交通流量的整体结构特征.接下来,设计了局部卷积多头自注意力机制来获取交通数据的动态时间相关性,实现在多种时间窗口下的准确流量预测.最后,在四种真实交通数据上的实验结果证明了本文模型的有效性和准确性.     

Indexing in-network trajectory flows

Indexing moving objects (MO) is a hot topic in the field of moving objects databases since many years. An impressive number of access methods have been proposed to optimize the processing of MO-related queries. Several methods have focused on spatio-temporal range queries, which represent the foundation of MO trajectory queries. Surprisingly, only a few of them consider that the objects movements are constrained. This is an important aspect for several reasons ranging from better capturing the relationship between the trajectory and the network space to more accurate trajectory representation with lower storage requirements. In this paper, we propose T-PARINET, an access method to efficiently retrieve the trajectories of objects moving in networks. T-PARINET is designed for continuous indexing of trajectory data flows. The cornerstone of T-PARINET is PARINET, an efficient index for historical trajectory data. The structure of PARINET is based on a combination of graph partitioning and a set of composite B⁺-tree local indexes. Because the network can be modeled using graphs, the partitioning of the trajectory data makes use of graph partitioning theory and can be tuned for a given query load and a given data distribution in the network space. The tuning process is built on a good quality cost model that is supplied with PARINET. The advantage of having a cost model is twofold; it allows a better integration of the index into the query optimizer of any DBMS, and it permits tuning the index structure for better performance. The tuning process can be performed before the index creation in the case of historical data or online in the case of indexing data flows. In fact, massive online updates can degrade the index quality, which can be measured by the cost model. We propose a specific maintenance process that results into T-PARINET. We study different types of queries and provide an optimized configuration for several scenarios. T-PARINET can easily be integrated into any RDBMS, which is an essential asset particularly for industrial or commercial applications. The experimental evaluation under an off-the-shelf DBMS shows that our method is robust. It also significantly outperforms the reference R-tree-based access methods for in-network trajectory databases.     

Graph structure analysis based on complex network

In this paper, we propose a novel method to characterize graph structures based on complex network model. First, we show that a structural graph can be modeled as a small-world complex network, and, then, Complex Network Characteristics (including topological and dynamic characteristics) Representation of a Graph (CNCRG) is obtained. Based on these characteristics, graph classification/clustering for objects viewed from different directions and characteristic views identification for single objects are investigated on one synthetic image dataset and two real image datasets. Our experimental results showed that CNCRG achieves better object classification/clustering performance and also provides well-structured view spaces based on multi-dimensional scaling (MDS) and principal component analysis (PCA) embedding methods for graphs extracted from 2D views of 3D objects.     

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

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

基于深度学习的智能交通系统通信网络脆弱性检测

智能交通系统是集群智能技术的典型应用之一. 为解决现有智能交通通信网络脆弱性检测方法复杂度高、实时性差的问题, 提出引入深度学习技术对网络脆弱性检测方法进行设计. 先利用多智能体网络协同和消息传输机制与智能交通系统车辆间协作通信网络的共通性, 将智能交通系统通信图脆弱性检测问题建模为对多智能体网络r-鲁棒值的求解问题. 再针对随网络节点数目增多r-鲁棒值求解成NP难问题, 设计给出一种融入残差网络的深度学习算法, 将鲁棒值求解问题转化为深度学习图分类问题. 所提算法可有效应对动态多变的智能交通通信网络并对其实现快速精准的脆弱性检测. 最后通过一组典型交通场景的仿真实验验证本文所提方法的有效性.     

A generic data model for moving objects

Moving objects databases should be able to manage trips that pass through several real world environments, e.g., road network, indoor. However, the current data models only deal with the movement in one situation and cannot represent comprehensive trips for humans who can move inside a building, walk on the pavement, drive on the road, take the public vehicles (bus or train), etc. As a result, existing queries are solely limited to one environment. In this paper, we design a data model that is able to represent moving objects in multiple environments in order to support novel queries on trips in different surroundings and various transportation modes (e.g., Car, Walk, Bus). A generic and precise location representation is proposed that can apply in all environments. The idea is to let the space for moving objects be covered by a set of so-called infrastructures each of which corresponds to an environment and defines the available places for moving objects. Then, the location is represented by referencing to the infrastructure. We formulate the concept of space and infrastructure and propose the methodology to represent moving objects in different environments with the integration of precise transportation modes. Due to different infrastructure characteristics, a set of novel data types is defined to represent infrastructure components. To efficiently support new queries, we design a group of operators to access the data. We present how such a data model is implemented in a database system and report the experimental results. The new model is designed with attention to the data models of previous work for free space and road networks to have a consistent type system and framework of operators. In this way, a powerful set of generic query operations is available for querying, together with those dealing with infrastructures and transportation modes. We demonstrate these capabilities by formulating a set of sophisticated queries across all infrastructures.