Trajectories of Moving Objects on a Network: Detection of Similarities,Visualization of Relations,and Classification of Trajectories

Development in techniques of spatial data acquisition enables us to easily record the trajectories of moving objects. Movement of human beings, animals, and birds can be captured by GPS loggers. The obtained data are analyzed by visualization, clustering, and classification to detect patterns frequently or rarely found in trajectories. To extract a wider variety of patterns in analysis, this article proposes a new method for analyzing trajectories on a network space. The method first extracts primary routes as subparts of trajectories. The topological relations among primary routes and trajectories are visualized as both a map and a graph‐based diagram. They permit us to understand the spatial and topological relations among the primary routes and trajectories at both global and local scales. The graph‐based diagram also permits us to classify trajectories. The representativeness of primary routes is evaluated by two numerical measures. The method is applied to the analysis of daily travel behavior of one of the authors. Technical soundness of the method is discussed as well as empirical findings.     

CONSTAnT – A Conceptual Data Model for Semantic Trajectories of Moving Objects

Several works have been proposed in the last few years for raw trajectory data analysis, and some attempts have been made to define trajectories from a more semantic point of view. Semantic trajectory data analysis has received significant attention recently, but the formal definition of semantic trajectory, the set of aspects that should be considered to semantically enrich trajectories and a conceptual data model integrating these aspects from a broad sense is still missing. This article presents a semantic trajectory conceptual data model named CONSTAnT, which defines the most important aspects of semantic trajectories. We believe that this model will be the foundation for the design of semantic trajectory databases, where several aspects that make a trajectory “semantic” are taken into account. The proposed model includes the concepts of semantic subtrajectory, semantic points, geographical places, events, goals, environment and behavior, to create a general concept of semantic trajectory. The proposed model is the result of several years of work by the authors in an effort to add more semantics to raw trajectory data for real applications. Two application examples and different queries show the flexibility of the model for different domains.     

Inferring trip purposes and uncovering travel patterns from taxi trajectory data

Global positioning system-enabled vehicles provide an efficient way to obtain large quantities of movement data for individuals. However, the raw data usually lack activity information, which is highly valuable for a range of applications and services. This study provides a novel and practical framework for inferring the trip purposes of taxi passengers such that the semantics of taxi trajectory data can be enriched. The probability of points of interest to be visited is modeled by Bayes’ rules, which take both spatial and temporal constraints into consideration. Combining this approach with Monte Carlo simulations, we conduct a study on Shanghai taxi trajectory data. Our results closely approximate the residents’ travel survey data in Shanghai. Furthermore, we reveal the spatiotemporal characteristics of nine daily activity types based on inference results, including their temporal regularities, spatial dynamics, and distributions of trip lengths and directions. In the era of big data, we encounter the dilemma of “trajectory data rich but activity information poor” when investigating human movements from various data sources. This study presents a promising step toward mining abundant activity information from individuals’ trajectories.     

Extending F‐Perceptory to model fuzzy objects with composite geometries for GIS

When analyzing spatial issues, geographers are often confronted with many problems with regard to the imprecision of the available information. It is necessary to develop representation and design methods which are suited to imprecise spatiotemporal data. This led to the recent proposal of the F‐Perceptory approach. F‐Perceptory models fuzzy primitive geometries that are appropriate in representing homogeneous regions. However, the real world often contains cases that are much more complex, describing geographic features with composite structures such as a geometry aggregation or combination. From a conceptual point of view, these cases have not yet been managed with F‐Perceptory. This article proposes modeling fuzzy geographic objects with composite geometries, by extending the pictographic language of F‐Perceptory and its mapping to the Unified Modeling Language (UML) necessary to manage them in object/relational databases. Until now, the most commonly used object modeling tools have not considered imprecise data. The extended F‐Perceptory is implemented under a UML‐based modeling tool in order to support users in fuzzy conceptual data modeling. In addition, in order to properly define the related database design, an automatic derivation process is implemented to generate the fuzzy database model.     

Integrated compression of vehicle spatio‐temporal trajectories under the road stroke network constraint

With fast growth of all kinds of trajectory datasets, how to effectively manage the trajectory data of moving objects has received a lot of attention. This study proposes a spatio‐temporal data integrated compression method of vehicle trajectories based on stroke paths coding compression under the road stroke network constraint. The road stroke network is first constructed according to the principle of continuous coherence in Gestalt psychology, and then two types of Huffman tree—a road strokes Huffman tree and a stroke paths Huffman tree—are built, based respectively on the importance function of road strokes and vehicle visiting frequency of stroke paths. After the vehicle trajectories are map matched to the spatial paths in the road network, the Huffman codes of the road strokes and stroke paths are used to compress the trajectory spatial paths. An opening window algorithm is used to simplify the trajectory temporal data depicted on a time–distance polyline by setting the maximum allowable speed difference as the threshold. Through analysis of the relative spatio‐temporal relationship between the preceding and latter feature tracking points, the spatio‐temporal data of the feature tracking points are all converted to binary codes together, accordingly achieving integrated compression of trajectory spatio‐temporal data. A series of comparative experiments between the proposed method and representative state‐of‐the‐art methods are carried out on a real massive taxi trajectory dataset from five aspects, and the experimental results indicate that our method has the highest compression ratio. Meanwhile, this method also has favorable performance in other aspects: compression and decompression time overhead, storage space overhead, and historical dataset training time overhead.     

Ontology‐based Qualitative Feature Analysis: Bays as a Case Study

A methodology for analyzing geographic data using the techniques of: (1) qualitative geometric abstraction; and (2) ontological analysis of geographic features is described. The first technique is a bottom‐up approach to extract qualitative spatial relations from geographic representations (raster or vector) while the second technique is a top‐down approach to determine which qualitative relations can possibly hold between the parts of the geographic features. The process of analyzing geographic data includes the extraction of both the features and the qualitative relations among features. These qualitative relations are then used to classify the geographic features within the “space” of ontological possibilities. In this article bays in Wisconsin and their cartographic representation are used as a running example and the subject of a case study.     

An intersection‐based trajectory‐region movement study

In order to better understand the movement of an object with respect to a region, we propose a formal model of the evolving spatial relationships that transition between local topologies with respect to a trajectory and a region as well as develop a querying mechanism to analyze movement patterns. We summarize 12 types of local topologies built on trajectory‐region intersections, and derive their transition graph; then we capture and model evolving local topologies with two types of trajectory‐region strings, a movement string and a stop‐move string. The stop‐move string encodes the stop information further during a trajectory than the movement string. Such a string‐format expression of trajectory‐region movement, although conceptually simple, carries unprecedented information for effectively interpreting how trajectories move with respect to regions. We also design the corresponding Finite State Automations for a movement string as well as a stop‐move string, which are used not only to recognize the language of trajectory‐region strings, but also to deal effectively with trajectory‐region pattern queries. When annotated with the time information of stops and intersections, a trajectory‐region movement snapshot and its evolution during a time interval can be inferred, and even the relationships among trajectories with respect to the same region can be explored.     

Spatiotemporal retrieval of dynamic video object trajectories in geographical scenes

Current studies on video trajectory retrieval focus on the retrieval and analysis of image content, neglecting the gap between the spatiotemporal continuity of retrieval conditions and the spatiotemporal discontinuity of multi‐camera video trajectories. In this study, we propose a method for the spatiotemporal retrieval of dynamic video object trajectories in geographic scenes. Based on the camera calibration, the proposed method organizes the scene, cameras, and trajectories, constructs the spatiotemporal constraints, and queries the trajectories using two measures: camera‐by‐camera retrieval and global trajectory retrieval. The proposed method was verified through experiments, and the results demonstrate that both measures can query trajectories effectively and reduce the spatiotemporal video review range under different spatiotemporal constraints. Furthermore, compared with camera‐by‐camera retrieval, global trajectory retrieval can reduce the spatiotemporal video review range further and return more accurate results. The proposed method may provide support for the spatial analysis and understanding of surveillance video data.     

移动轨迹聚类方法研究综述

轨迹数据是人类移动行为的表征,能够映射出人的出行模式和社会属性等信息。怎样有效挖掘轨迹数据蕴藏的人类活动规律一直是研究的热点。通过轨迹聚类发现行为相似的类簇,从而探究群体的移动模式是轨迹挖掘和深度应用常见的方法之一。本文首先根据轨迹数据的特点,将轨迹数据模型分为轨迹点模型和轨迹段模型,并据此定义相应的相似性度量：空间相似性度量和时空相似性度量;然后,对两类模型的聚类方法进行了综述,并总结不同聚类算法的优缺点,以期为不同应用选取聚类算法提供科学依据;最后对移动轨迹数据聚类方法研究的发展趋势进行了讨论。     

Definitions of natural-language spatial relations: Combining topology and directions

Because SQL for querying data from spatial databases is ineffective, the query based on natural or visual language becomes an attractive research field gradually. However, how to define and represent natural languages related to spatial data are still gigantic problems. Because existing models of direction relations can't describe by use of some common concepts. First of all, detailed direction relations are proposed to describe the directions related to the interior of spatial objects, such as “east part of a region”, “east boundary of a region”, and so on. Secondly, by integrating the detailed directions with exterior direction relations and topological relations, several NLSRs are defined, such as “a road goes across the east part of a lake”, “a river goes along the east boundary of a province”, etc. Finally, based on the NLSRs abovementioned, a natural spatial query language (NSQL) is formed to retrieve data from spatial databases.     

Conflation of OpenStreetMap and Mobile Sports Tracking Data for Automatic Bicycle Routing

This article investigates how workout trajectories from a mobile sports tracking application can be used to provide automatic route suggestions for bicyclists. We apply a Hidden Markov Model (HMM)‐based method for matching cycling tracks to a “bicycle network” extracted from crowdsourced OpenStreetMap (OSM) data, and evaluate its effective differences in terms of optimal routing compared with a simple geometric point‐to‐curve method. OSM has quickly established itself as a popular resource for bicycle routing; however, its high‐level of detail presents challenges for its applicability to popularity‐based routing. We propose a solution where bikeways are prioritized in map‐matching, achieving good performance; the HMM‐based method matched correctly on average 94% of the route length. In addition, we show that the extremely biased nature of the trajectory dataset, which is typical of volunteered user‐generated data, can be of high importance in terms of popularity‐based routing. Most computed routes diverged depending on whether the number of users or number of tracks was used as an indicator of popularity, which may imply varying preferences among different types of cyclists. Revising the number of tracks by diversity of users to surmount local biases in the data had a more limited effect on routing.     

MASTER: A multiple aspect view on trajectories

For many years trajectory data have been treated as sequences of space‐time points or stops and moves. However, with the explosion of the Internet of Things and the flood of big data generated on the Internet, such as weather channels and social network interactions, which can be used to enrich mobility data, trajectories become more and more complex, with multiple and heterogeneous data dimensions. The main challenge is how to integrate all this information with trajectories. In this article we introduce a new concept of trajectory, called multiple aspect trajectory, propose a robust conceptual and logical data model that supports a vast range of applications, and, differently from state‐of‐the‐art methods, we propose a storage solution for efficient multiple aspect trajectory queries. The main strength of our data model is the combination of simplicity and expressive power to represent heterogeneous aspects, ranging from simple labels to complex objects. We evaluate the proposed model in a tourism scenario and compare its query performance against the state‐of‐the‐art spatio‐temporal database SECONDO extension for symbolic trajectories.     

A Spatio‐Temporal Graph Model for Marine Dune Dynamics Analysis and Representation

Defining a model for the representation and the analysis of spatio‐temporal dynamics remains an open domain in geographical information sciences. In this article we investigate a spatio‐temporal graph‐based model dedicated to managing and extracting sets of geographical entities related in space and time. The approach is based on spatial and temporal local relations between neighboring entities during consecutive times. The model allows us to extract sets of connected entities distant in time and space over long periods and large spaces. From GIS concepts and qualitative reasoning on space and time, we combine the graph model with a dedicated spatial database. It includes information on geometry and geomorphometric parameters, and on spatial and temporal relations. This allows us to extend classical measurements of spatial parameters, with comparisons of entities linked by complex relations in space and time. As a case study, we show how the model suggests an efficient representation of dunes dynamics on a nautical chart for safe navigation.     

符合认知规律的时空轨迹融合与路网生成方法

以行驶在城市大街小巷的出租车GPS时空轨迹数据为研究对象,研究了符合"感知—认知—经验"认知规律3层次的轨迹融合与路网生成方法,提出了基于Delaunay三角网的时空轨迹融合模型,实现了从GPS时空轨迹中对符合认知规律需求的路网信息的获取,并以武汉市出租车GPS轨迹为试验,实现了对武汉市出租车时空轨迹的融合与武汉市路网数据的生成,证明了该方法的有效性。     

Interactive visual cluster detection in large geospatial datasets based on dynamic density volume visualization

The emerging spatial big data (e.g. detailed spatial trajectories, geo-referenced social media data) provide tremendous opportunities for GIScientists and geographers. However, their large volume also poses challenges to existing spatial data analytical techniques (including visual analytical techniques). This article presents an interactive visual approach to detect clusters from those emerging data sets based on dynamic density volume visualization in a three-dimensional space (two spatial dimensions plus a third temporal or thematic dimension of interest). Cluster can be visually discovered through dynamic adjustment of density to colour/opacity mapping and extracted through flexible selection tools. The approach was tested on a large simulated data-set and a spatial trajectory data-set. The results show that the approach can overcome the visual clotting problem in traditional visualization tools caused by large data volume and facilitate the involvement of domain knowledge in analysis. It can effectively support visual cluster detection in the emerging large geospatial data sets.     

Exact Computational Methods for Calculating Distances Between Objects in a Cartographic Database

Most existing spatial analytic techniques use a simplified, point-based representation of spatial objects. This facilitates tractability of the standard computational procedures for many spatial measures, for example, distances between spatial objects. The increasing spatial data handling and manipulation capabilities of geographic information systems (GIS), however, allow a re-examination of fundamental representations and measures in spatial analysis. This article develops exact computational procedures for calculating the average, minimum, and maximum distances between pairings of the three geometric primitives (points, lines, and polygons) when these objects are stored in the vector GIS data model. These procedures are “exact” in the sense that they are completely accurate, subject to the database representation. This article also provides example results from average distance calculations for a generic spatial database.     

Towards semantic‐aware multiple‐aspect trajectory similarity measuring

The large amount of semantically rich mobility data becoming available in the era of big data has led to a need for new trajectory similarity measures. In the context of multiple‐aspect trajectories, where mobility data are enriched with several semantic dimensions, current state‐of‐the‐art approaches present some limitations concerning the relationships between attributes and their semantics. Existing works are either too strict, requiring a match on all attributes, or too flexible, considering all attributes as independent. In this article we propose MUITAS, a novel similarity measure for a new type of trajectory data with heterogeneous semantic dimensions, which takes into account the semantic relationship between attributes, thus filling the gap of the current trajectory similarity methods. We evaluate MUITAS over two real datasets of multiple‐aspect social media and GPS trajectories. With precision at recall and clustering techniques, we show that MUITAS is the most robust measure for multiple‐aspect trajectories.     

Moving Code in Spatial Data Infrastructures – Web Service Based Deployment of Geoprocessing Algorithms

This article proposes a concept for offering complex geoprocessing functionality in service‐based Spatial Data Infrastructures (SDI). Today, geoprocessing in SDI is typically realized in a data driven manner. Applying the suggested “moving code” approach in a case study in the field of Spatial Decision Support proves its applicability. The proposed solution is analyzed and assessed in terms of gained efficiency, performance behavior and support for distributed development of geoprocessing functionality. In data and computation intensive SDI applications the deployment of moving code proves to be beneficial.     

车辆GPS轨迹兴趣区域提取算法研究

车辆行驶轨迹是驾驶员主观意愿和路网客观约束综合作用的结果,从海量轨迹中挖掘兴趣区域可为车辆提供更深层次、更有效的位置服务。文中深入分析车辆GPS轨迹特征,在基于时间的聚类算法中引入路网约束,实现车辆GPS轨迹的兴趣点提取和噪点剔除,基于DBSCAN算法生成兴趣区域,采用Google Geocoding反向地理编码发掘并合并语义重复区域,在语义层次上实现兴趣区域提取。实验表明,该算法可在语义层次有效提取兴趣区域。