Data mining of network-constrained trajectories has broad applications in the GIScience field. The calculation of a complete trajectory similarity matrix is a key step in various data mining algorithms. However, computing this matrix is computationally intensive for large datasets, as it involves numerous point-to-point shortest-path (PPSP) queries. To tackle this issue, we propose a new spatiotemporal construct called the space-time tree, which directly delineates the network distance from a query trajectory to any network space-time point. By constructing the space-time tree, we can efficiently compute the trajectory similarity matrix without additional PPSP queries. The space-time tree supports several similarity metrics, including closest pair distance, furthest pair distance, longest common subsequence (LCSS), and distance-weighted LCSS. It can further integrate with advanced spatiotemporal query techniques for scalable partial trajectory similarity matrix calculations. A case study using real datasets was conducted to apply the space-time tree in the trajectory clustering application. The results show that the space-time tree completed the clustering task on 0.5 million trajectories within 49 minutes, achieving a nearly 147-fold speedup compared to state-of-the-art methods.

Ensuring the correctness of road network data is critical for navigation, traffic control and urban planning. Errors like missing roads and absent connections can hinder its quality. Trajectory data emerges as a cost-effective source to uncover such errors. Existing methods often analyze the mismatches between trajectories and road networks to identify specific errors. They heavily rely on manually established rules and fail to fully leverage the diverse patterns of trajectories and the underlying road network structure. The article introduces a sequential classification approach to detect diverse road network errors. It starts with partial map matching (PMM) to associate trajectories with a road network, allowing unmatched portions. Context features are subsequently extracted by encoding patterns in the map matching (MM) outputs, raw trajectories and road network. Finally, a bidirectional recurrent neural network (BiRNN) model is trained to identify the network error category for each trajectory point. Experiments were performed on detecting errors in OpenStreetMap (OSM) road network with a real-world trajectory dataset. It demonstrates that the proposed method achieves accuracy over 96%, significantly surpassing four baselines. An ablation study confirms the necessity of considering different types of context features. This method advances error detection by effectively utilizing trajectories in identifying diverse network errors.

Clustering the trajectories of vehicles moving on road networks is a key data mining technique for understanding human mobility patterns, as well as their interactions with urban environments. The development of efficient and scalable trajectory clustering algorithms, however, still faces challenges because of the computational costs when measuring similarities among a large number of network-constrained trajectories. To address this problem, a novel trajectory clustering framework based on the well-developed Density-Based Spatial Clustering of Applications with Noise (DBSCAN) approach is proposed. This proposed framework accurately quantifies similarities using a trajectory representation of continuous polylines in the space and time dimensions, and does not require trajectory discretization. Further, the proposed framework utilizes the space-time buffering concept to formulate ε-neighborhood queries that directly retrieve the ε-neighbors of trajectories and thus avoids computing a trajectory similarity matrix. State-of-the-art trajectory databases and index structures are incorporated to further improve trajectory clustering performance. A comprehensive case study was carried out using an open dataset of 20,161 trajectories. Results show that the proposed framework efficiently executed trajectory clustering on the large test dataset within 3 min. This was approximately 2,700 times faster than existing DBSCAN algorithms.

The availability of Spatiotemporal Big Data has provided a golden opportunity for time geographical studies that have long been constrained by the lack of individual-level data. However, how to store, manage, and query a huge number of time geographic entities effectively and efficiently with complex spatiotemporal characteristics and relationships poses a significant challenge to contemporary GIS platforms. In this article, a hierarchical compressed linear reference (CLR) model is proposed to transform network-constrained time geographic entities from three-dimensional (3D) (x, y, t) space into two-dimensional (2D) space. Accordingly, time geographic entities can be represented as 2D spatial entities and stored in a classical spatial database. The proposed CLR model supports a hierarchical linear reference system (LRS) including not only underlying a link-based LRS but also multiple higher-level route-based LRSs. In addition, an LRS-based spatiotemporal index structure is developed to index both time geographic entities and the corresponding hierarchical network. The results of computational experiments on large datasets of space–time paths and prisms show that the proposed hierarchical CLR model is effective at storing and managing time geographic entities in road networks. The developed index structure achieves satisfactory query performance in milliseconds on large datasets of time geographic entities.

Existing spatial clustering methods primarily focus on points distributed in planar space. However, occurrence locations and background processes of most human mobility events within cities are constrained by the road network space. Here we describe a density-based clustering approach for objectively detecting clusters in network-constrained point events. First, the network-constrained Delaunay triangulation is constructed to facilitate the measurement of network distances between points. Then, a combination of network kernel density estimation and potential entropy is executed to determine the optimal neighbourhood size. Furthermore, all network-constrained events are tested under a null hypothesis to statistically identify core points with significantly high densities. Finally, spatial clusters can be formed by expanding from the identified core points. Experimental comparisons performed on the origin and destination points of taxis in Beijing demonstrate that the proposed method can ascertain network-constrained clusters precisely and significantly. The resulting time-dependent patterns of clusters will be informative for taxi route selections in the future.

Precipitation stations are important components of a hydrological monitoring network. Given their critical role in rainfall forecasting and flood warnings, along with limited observation resources, determining the optimal locations to deploy precipitation stations presents an important problem. In this paper, we use a maximal covering location problem to identify the best precipitation station sites. Considering the terrain conditions and the characteristics of a rainfall network, the original maximal covering location model is modified with the introduction of a set of additional constraints. The minimum density requirement is used to determine a precipitation station’s coverage range, and three weighting schemes are used to evaluate each demand object’s covering priority. As a typical mountainous watershed with high annual precipitation, the Jinsha River Basin is selected as the study area to test the applicability of the proposed method. Results show that the proposed method is effective for precipitation station configuration optimization, and the model solution achieves higher coverage than the real-world deployment. Compared with the commercial solver CPLEX, a genetic algorithm-based heuristic can significantly reduce the computation time when the problem size is large. Several deployment strategies are also discussed for establishing the optimal configuration of precipitation stations.

Polygonal vector data are important for representing countries, lakes, residential settlements, and other polygonal features. The proper representation of polygonal vector data is the basis of efficient rendering and picking and quick access and display of the analysis results based on polygons (e.g., 3D overlaying and surface area measurement in mountainous areas) in a virtual globe. However, polygonal vector data are displayed using texture-based or boundary-based approaches in most existing virtual globes. The texture-based approach cannot easily support interactive operations (e.g., picking) and spatial analysis (e.g., adjacency analysis and spatial measurement). The boundary-based approach treats the holes as independent features; however, it is difficult to recognize which boundaries constitute a polygon. Further research is needed on how to better organize the polygons to support efficient rendering, picking, and analysis in a virtual globe. In this article, we propose two methods to drape interior filled 2D polygons onto a multi-resolution 3D terrain. Both proposed methods combine polygon clipping and polygon triangulation. The difference between the two methods is in the way holes are eliminated. Method 1 recursively subdivides a terrain triangle until the child-triangles contain no holes; every resulting clipped polygon, which is then triangulated, contains no holes. Method 2 directly clips a polygon against a terrain triangle and creates bridge edges to transform the resulting polygons with holes to degenerate polygons that are further triangulated. The experimental results demonstrate that both proposed methods can efficiently process polygons with holes resulting in appropriate numbers of triangles. The processed interior-filled polygons remain close to the terrain surface in a virtual globe. Both proposed methods support real-time rendering of polygonal vector data in a virtual globe.