Data Modelling And Clustering Of Network Space-time Entities For Computational Time Geographical Analysis

Time geography provides a powerful analytical framework for understanding individual-level activity-travel behaviors under various constraints,and is widely applied in fields such as urban planning.The wide use of location-aware technologies in our daily life has greatly expanded our capability to collect large-scale individual-level movement data at the fine spatiotemporal resolution,providing an ideal data source for time geography and propelling the flourishing of computational time geography research.However,the large volume of individual activity-travel movement data is multidimensional and highly dynamic,and often limited by urban multi-modal transportation networks,so how to efficiently store,manage,and analyze a large volume of individual activity-travel movement data is a key scientific problem in the current GIS(Geographic Information Science)field.To address the limitations of the existing literature on the lack of computational time geography analysis techniques in the era of big data,it is important to research the modeling and efficient analysis methods of time geography entities.Based on the above background,this thesis proposes a spatiotemporal data model,index structure,and efficient clustering algorithms for network-constrained time geographic entities,including space-time paths as well as space-time prisms,to support computational time geography research.The main research of this thesis consists of the following four parts:(1)A spatiotemporal data model and index structure based on the hierarchical compressed linear reference(HCLR)technique are proposed.Firstly,a spatiotemporal data model based on the HCLR technique is proposed,through which the time geographic entities,such as space-time prisms,can be equivalently transformed from three-dimensional(x,y,t)space to two-dimensional(z,t)space,and stored in a spatial database together with a hierarchical transportation network.On this basis,the spatiotemporal index based on the HCLR technique is proposed to realize the efficient spatiotemporal query of time geographic entities.Finally,the storage performance of the HCLR model and the query efficiency of the HCLR index are analyzed by using taxi trajectory data and a synthetic Origin-Destination dataset in Wuhan,China.The experimental results show that the HCLR model can reduce the storage space for storing time geographic entities by up to 33%;the HCLR index structure achieves satisfactory query performance in milliseconds on large datasets of time geographic entities,which meets the demand for efficient storage and query of massive time geographic entities.(2)An efficient and scalable DBSCAN framework for clustering network space-time paths is proposed.Firstly,the continuous version of distance metrics is introduced to accurately quantify the spatiotemporal distance of the network space-time path.Then the nearest neighbors of paths are directly retrieved from-neighborhood queries using corresponding distance metrics to avoid the computational burden involved in computing the space-time path distance matrix.The CLR(Compressed Linear Reference)data model and index structures are further incorporated to implement-neighborhood queries.Comprehensive case studies are carried out using an open large trajectory dataset,T-Drive.Results show that the proposed framework efficiently executed space-time path clustering on the large test dataset within 3 min.This was approximately 2,700 times faster than existing DBSCAN algorithms and meets the demand for efficient processing of massive network space-time paths.(3)The concept of a space-time tree and an efficient hierarchical clustering framework for network space-time paths are proposed.Firstly,the space-time tree is proposed,and a geo-computational algorithm is proposed based on the constructed space-time tree to accurately calculate the space-time path distance.Then an efficient hierarchical clustering framework based on spatiotemporal query and space-time tree is proposed.The framework uses-neighborhood query to filter space-time paths,and then uses the space-time tree to accurately calculate the distance to space-time paths in the-neighborhood.By combining the spatiotemporal query and the space-time tree,the computational complexity of the existing space-time path hierarchical clustering algorithm is reduced from(||~2×||÷2)to(||×||).In addition,the developed framework makes use of the advanced HCLR data models,HCLR index structures and spatiotemporal query techniques,which can efficiently retrieve proximal paths whose spatiotemporal distances are less than a given threshold.In this way,the developed framework can improve the clustering performance by inputting a connectivity matrix that defines for each sample the neighboring samples using only spatiotemporal proximal paths.Comprehensive case studies are carried out using a large trajectory dataset from Wuhan,China.Results of case study show that the commonly used discrete methods can introduce remarkable bias on the path distance measurement.Results also demonstrate the promising performance of the developed path clustering framework.It can cluster space-time paths of the testing large dataset in about 3 minutes,which is approximately 600 times faster than the previous method and meets the demand for efficient processing of massive network space-time paths.(4)An efficient and scalable DBSCAN framework for clustering network space-time prisms is proposed.Firstly,the continuous version of distance metric is proposed to accurately quantify spatiotemporal distance of network space-time prism.Then the nearest neighbors of network space-time prisms are directly retrieved from-neighborhood queries using corresponding distance metrics.The HCLR data model and index structures are further incorporated to implement-neighborhood queries.Comprehensive case studies are carried out using a large Origin-Destination dataset in Wuhan,China.Results of case study show that the proposed framework efficiently executed space-time prism clustering on the large test dataset in about 40 minutes and meets the demand for efficient processing of massive network space-time prisms.