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

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

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

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

Update-efficient indexing of moving objects in road networks

Recent advances in wireless sensor networks and positioning technologies have boosted new applications that manage moving objects. In such applications, a dynamic index is often built to expedite evaluation of spatial queries. However, the development of efficient indexes is a challenge due to frequent object movement. In this paper, we propose a new update-efficient index method for moving objects in road networks. We introduce a dynamic data structure, called adaptive unit, to group neighboring objects with similar movement patterns. To reduce updates, an adaptive unit captures the movement bounds of the objects based on a prediction method, which considers road-network constraints and the stochastic traffic behavior. A spatial index (e.g., R-tree) for the road network is then built over the adaptive unit structures. Simulation experiments, carried on two different datasets, show that an adaptive-unit based index is efficient for both updating and querying performances.

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.     

Efficient moving <Emphasis Type="Italic">k</Emphasis> nearest neighbor queries over line segment objects

The growing need for location based services motivates the moving k nearest neighbor query (MkNN), which requires to find the k nearest neighbors of a moving query point continuously. In most existing solutions, data objects are abstracted as points. However, lots of real-world data objects, such as roads, rivers or pipelines, should be reasonably modeled as line segments or polyline segments. In this paper, we present LV*-Diagram to handle MkNN queries over line segment data objects. LV*-Diagram dynamically constructs a safe region. The query results remain unchanged if the query point is in the safe region, and hence, the computation cost of the server is greatly reduced. Experimental results show that our approach significantly outperforms the baseline method w.r.t. CPU load, I/O, and communication costs.     

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

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

一种构建于DSM的移动对象的全时态索引方法

移动对象索引技术是移动对象数据库这个新兴的热点领域中的关键技术之一.针对该技术处理数据的繁琐复杂特性,提出构建于DSM的移动对象索引方法 DSM_MSMON,在分布式系统中并行的管理移动对象的信息,支持更新和查询操作.DSM_MSMON统一了单机和多机的内存管理策略,解决了DSM系统中的数据定位、一致性维护、负载平衡和可扩充性等主要问题,有效地提高了移动对象索引的效率.文中给出DSM_MSMON的设计思想和模型,并分析了DSM_MSMON的关键技术和程序流程.实验结果表明,该方法要优于MSMON结构.     

Direction-aware KNN queries for moving objects in a road network

Recently more and more people focus on k-nearest neighbor (KNN) query processing over moving objects in road networks, e.g., taxi hailing and ride sharing. However, as far as we know, the existing k-nearest neighbor (KNN) queries take distance as the major criteria for nearest neighbor objects, even without taking direction into consideration. The main issue with existing methods is that moving objects change their locations and directions frequently over time, so the information updates cannot be processed in time and they run the risk of retrieving the incorrect KNN results. They may fail to meet users’ needs in certain scenarios, especially in the case of querying k-nearest neighbors for moving objects in a road network. In order to find the top k-nearest objects moving toward a query point, this paper presents a novel algorithm for direction-aware KNN (DAKNN) queries for moving objects in a road network. In this method, R-tree and simple grid are firstly used as the underlying index structure, where the R-tree is used for indexing the static road network and the simple grid is used for indexing the moving objects. Then, it introduces the notion of “azimuth” to represent the moving direction of objects in a road network, and presents a novel local network expansion method to quickly judge the direction of the moving objects. By considering whether a moving object is moving farther away from or getting closer to a query point, the object that is definitely not in the KNN result set is effectively excluded. Thus, we can reduce the communication cost, meanwhile simplify the computation of moving direction between moving objects and query point. Comprehensive experiments are conducted and the results show that our algorithm can achieve real-time and efficient queries in retrieving objects moving toward query point in a road network.

     

Example‐Driven Procedural Urban Roads

Synthesizing and exploring large‐scale realistic urban road networks is beneficial to 3D content creation, traffic animation and urban planning. In this paper, we present an interactive tool that allows untrained users to design roads with complex realistic details and styles. Roads are generated by growing a geometric graph. During a sketching phase, the user specifies the target area and the examples. During a growing phase, two types of growth are effectively applied to generate roads in the target area; example‐based growth uses patches extracted from the source example to generate roads that preserve some interesting structures in the example road networks; procedural‐based growth uses the statistical information of the source example while effectively adapting the roads to the underlying terrain and the already generated roads. User‐specified warping, blending and interpolation operations are used at will to produce new road network designs that are inspired by the examples. Finally, our method computes city blocks, individual parcels and plausible building and tree geometries. We have used our approach to create road networks covering up to 200 and containing over 3500 km of roads.