Integrating Algebraic Multigrid Method In Spatial Aggregation And Visualization Of Massive Trajectory Data

Recent advances in location-aware and communication technologies enable the easy collection of trajectories of moving entities.With the development of smart cities,a large amount of trajectory data can be used in different application domains such as urban planning,transportation and environment management.The analysis of these trajectories has mainly focused on discovering movement patterns of people and visual analysis of these data can present the spatio-temporal changes and the mining of movement patterns.However,visualizing this complex and large number of trajectories is a big challenging.Traditional flow visualizations usually fail due to massive interactions and overlapping between trajectories which make the display heavily cluttered and illegible.So it is particularly important to adopt appropriate aggregation methods to simplify trajectory data.The cell-phone signaling records of Beijing within one working day is taken as research data and we propose a new trajectory simplification method based on algebraic multigrid method,then visualizing the simplified trajectory data with flow map and analyzing the human movement pattern of Beijing.In the comparison with other spatial clustering methods(such as k-means clustering and DBSCAN clustering),the advantage of this paper lies in reducing the uncertainty brought by the adjustment of parameters and constructing a multi-scale presentation of trajectory simplification data.The main research contents are as follows:After data cleaning and stay point detection,the user trajectories are segmented into OD links of different mobile phone base stations.Graph theory is introduced to regard the trajectory nodes as vertices and the connections between trajectories as edges to construct a complex network based on urban trajectories.The concept of in-out degree in the complex network is used to calculate the value of access degree of different trajectory points in Beijing.This index reflects the visiting heat of different trajectory nodes in a day,which is one of the parameters directly reflecting the importance of trajectory nodes.Secondly,the distance decay effect is considered in the relationship of edges,that is,the spatial interaction decreases with the increase of distance,so as to measure the spatial relationship between different adjacent trajectory points.Secondly,the mathematical iterative method of algebraic multigrid method(AMG)is used to extract the important nodes of the trajectory data network.According to the concept of strong connection in the AMG algorithm,the strength matrix is constructed from the trajectory data according to the two variables(distance and in-out degree).Then the strongly connected part of the trajectory network is filtered through each level of grid.These spatial representative nodes can be treat as important nodes in the city.Voronoi segmentation is carried out with them to simplify the city in the scale of geographical space,so as to achieve the aggregation of trajectory data based on spatial units.Through the comparison with the traditional PageRank and degree centrality methods,it is found that AMG method is more advanced in both the spatial representation and the importance of nodes because in the definition of strong connection point in the AMG method,the selected nodes is proportional to the in-out degree and inversely proportional to the distance.That is to say,the node selection takes into account the spatial representation,so the evaluation result by the AMG method is better than the other two methods.Finally,the traditional flow map is used to visualize the aggregated trajectory data.Different data presentation methods are used in designing flow map.Firstly,the flow direction of the whole aggregated data was presented without any direction,that is,the trajectory access flow between different regions was retained after space segmentation,but the flow direction was not distinguished,and the flow size in different sections was compared.Then,the flow map with direction and arrow indication is designed according,and the difference value of the flow between any two areas is compared according to the width of the flow edge.In order to reduce the occlusion between edges,the concepts of color gradient and one-direction arrow are adopted in the design.At the same time,in order to analyze the trajectory change pattern in different time periods,this study divided one day into morning peak,daytime activity time,evening peak and late night time according to the trajectory base station activation curve and weekday commuting mode within a day.By comparing the different time of flow map,the result is consistent with conventional wisdom that Beijing has a clear central structure.The spatial interaction intensity of the central urban area is obviously higher than that of the surrounding areas,the activity heat is higher during the day than the night,and the results further verify the validity of our trajectory data simplified method.