# An Arch-Bridge Topology-Based Expressway Network Structure and Automatic Generation
## 2 Literature Review
### Spatio-Temporal Trajectory Mining  
With the continuous development of GPS sensor technology, it has become easier to obtain vehicle GPS trajectory data with higher accuracy and richer feature information. As a result, many researchers have turned to using GPS trajectory data for road network generation. Currently, there are three main methods for road network generation based on GPS trajectory data: (1) point clustering, (2) kernel density estimation (KDE), and (3) cross-linking. Point clustering involves using clustering algorithms (such as k-means) to extract the edges and basic points of the road network from GPS sampling points, and then connecting these elements to form a road network. In early research, [PERSON] et al. [36] attempted to identify road networks based on low-precision GPS data. They used a k-means algorithm with background knowledge constraints to cluster GPS tracking data from vehicles to find lanes. In subsequent work, the same authors proposed a spatial clustering algorithm that could infer map connectivity structure from scratch, making the map refinement process completely independent of the initial input map. This more powerful lane clustering algorithm can handle lane segmentation and merging [37]. [PERSON] and [PERSON] [38] used the Bentley-Ottmann algorithm to convert GPS data into a graphical structure and then applied k-means clustering to identify lanes. [PERSON] and [PERSON] [39] applied clustering algorithms to mining environments, successfully identifying road networks even without clear road edges or lane markings. [PERSON] et al. [40] developed a Traj-Meanshift algorithm to denoise GPS points and an innovative graph-based road segment clustering algorithm that utilized prior information on road smoothness. A point clustering method based on DBSCAN was also used for map matching [41]. [PERSON] et al. [42] used the advancing front spatial clustering with Delaunay triangulation (ASCDT) method to perform spatial clustering and combined spatial semantic information to construct road structure and topological relationships. The kernel density estimation (KDE) method is commonly used for visualizing and analyzing spatial data, with the aim of understanding and potentially predicting event patterns [43]. Nowadays, researchers have also applied KDE in road network generation, where it first transforms individual samples or trajectories into a discretized image that represents the density of samples or segments at each pixel. Using binary thresholds, they produce a binary image of the roads within the area and find the centerline of the roads through various methods, such as Voronoi partitioning. [PERSON] et al. [44] utilized non-parametric kernel density estimation to analyze the probability density distribution of trajectory points and generate an improved map containing lane centerlines. [PERSON] et al. [45] combined heuristic techniques, using KDE aggregation to obtain road segments between intersections, with generation modeling to reconstruct the optimal road map. [PERSON] et al. [46] employed KDE to determine the lane centerlines of three types of roads, using low-precision GPS data collected by floating vehicles as input. [PERSON] et al. [47] utilized kernel density analysis to estimate trajectory density, evaluating the results of centerline extraction with a hidden Markov model and eliminating erroneously extracted road centerline segments. They then employed a road centerline thinning method and map matching algorithm to incrementally merge road centerlines to generate a road network. This method exhibits good robustness and does not require additional parameter tuning. The intersection connection method is a technique used to construct and update road networks. It involves detecting intersection vertices and connecting them with edges based on trajectory features such as direction and speed. The intersections are then identified by interpolating the geometric shapes of the trajectories. [PERSON] and [PERSON] [48]were among the first to use this method to construct maps.