Mining human mobility patterns from pervasive spatial and temporal data

Publication Year: 2018 Publication Type : Thesis

Abstract:


Recent advances in communication, sensors and processors have made pervasive systems more computationally powerful and increasingly popular. These systems are deployed everywhere all the time while remaining transparent. Take smartphones as an example; they have become an integral part of human life and people carry them wherever they go. Coupled with the popularity of pervasive systems and user tracking, this has opened up excellent opportunities to analyse human mobility. This can be applied to a broad range of location-based services such as smart navigation and recommendation systems. Data from pervasive systems has temporal, spatial and spatio-temporal aspects that can be leveraged for mining human mobility patterns. Temporal data such as time series from embedded sensors on smartphones does not usually have any information about locations, while time stamps are discarded in spatial data. The list of significant locations visited by the user is an example of spatial data. The third group of data is spatio-temporal data that has both temporal and spatial aspects such as users' trajectories. In this dissertation, we analyse human mobility by mining these three kinds of data. In each chapter, we look at a specific aspect to infer key information about users’ mobility including transition time detection, movement graph summarisation, and trajectory prediction. We analyse temporal information from time series data to extract transition times in daily activities. The transition times denote when user activities change such as when the user goes to work or when the user goes shopping. In addition to applications in location-based services, extracting the transition times helps us to understand human mobility patterns across the whole day. We tackle scalability to enable processing to take place on resource-constrained devices. We introduce Shrink as a new summarisation method to compress large scale graphs. Trajectories and movements of the user can be transformed into a graph in which each node represents stay points and each edge represents distance. Since this graph is very large, Shrink is used to reduce the size of the movement graph while preserving distances between nodes. The property that is preserved in the compressed graph, also known as the coarse graph, is the distance between the nodes. Shrink is a query friendly compression, which means the compressed graph can be queried without decompression. As the complexity of distance-based queries such as shortest path queries is highly dependent on the size of the graph, Shrink improves performance in terms of time and storage. We also investigate the effect of compression on the human mobility mining algorithms and show that the summarisation provides a trade-off between efficiency and granularity. We also analyse spatial-temporal data by predicting user trajectory based on historical data. Specifically, given the historical data and the user’s trajectory in the first part of the current day (e.g. trajectory in the morning), we predict how users will complete their trajectory in that particular day (e.g. predicting the trajectory for the rest of the day or the afternoon). The granularity of the predicted trajectory is the same as the granularity of the given trajectories. We emphasize that the predicted trajectory includes the sequence of future locations, the stay times, and the departure times. This enhances the user experience because by having the detailed trajectory in advance, location-based services can notify users about the consequence of the movement. In summary, this thesis contains efficient algorithms that can be applied to diverse aspects of pervasive signals for mining human mobility. The new algorithms are aimed at problems in transition time detection, summarisation, and prediction. The solutions address the scalability issues and can work in big pervasive temporal and spatial data effectively and accurately.


BibTex:

@phdthesis{SadriAmin2018Mhmp, title = {Mining human mobility patterns from pervasive spatial and temporal data},
    abstract = {Recent advances in communication, sensors and processors have made pervasive systems more computationally powerful and increasingly popular. These systems are deployed everywhere all the time while remaining transparent. Take smartphones as an example; they have become an integral part of human life and people carry them wherever they go. Coupled with the popularity of pervasive systems and user tracking, this has opened up excellent opportunities to analyse human mobility. This can be applied to a broad range of location-based services such as smart navigation and recommendation systems. Data from pervasive systems has temporal, spatial and spatio-temporal aspects that can be leveraged for mining human mobility patterns. Temporal data such as time series from embedded sensors on smartphones does not usually have any information about locations, while time stamps are discarded in spatial data. The list of significant locations visited by the user is an example of spatial data. The third group of data is spatio-temporal data that has both temporal and spatial aspects such as users' trajectories. In this dissertation, we analyse human mobility by mining these three kinds of data. In each chapter, we look at a specific aspect to infer key information about users’ mobility including transition time detection, movement graph summarisation, and trajectory prediction. We analyse temporal information from time series data to extract transition times in daily activities. The transition times denote when user activities change such as when the user goes to work or when the user goes shopping. In addition to applications in location-based services, extracting the transition times helps us to understand human mobility patterns across the whole day. We tackle scalability to enable processing to take place on resource-constrained devices. We introduce Shrink as a new summarisation method to compress large scale graphs. Trajectories and movements of the user can be transformed into a graph in which each node represents stay points and each edge represents distance. Since this graph is very large, Shrink is used to reduce the size of the movement graph while preserving distances between nodes. The property that is preserved in the compressed graph, also known as the coarse graph, is the distance between the nodes. Shrink is a query friendly compression, which means the compressed graph can be queried without decompression. As the complexity of distance-based queries such as shortest path queries is highly dependent on the size of the graph, Shrink improves performance in terms of time and storage. We also investigate the effect of compression on the human mobility mining algorithms and show that the summarisation provides a trade-off between efficiency and granularity. We also analyse spatial-temporal data by predicting user trajectory based on historical data. Specifically, given the historical data and the user’s trajectory in the first part of the current day (e.g. trajectory in the morning), we predict how users will complete their trajectory in that particular day (e.g. predicting the trajectory for the rest of the day or the afternoon). The granularity of the predicted trajectory is the same as the granularity of the given trajectories. We emphasize that the predicted trajectory includes the sequence of future locations, the stay times, and the departure times. This enhances the user experience because by having the detailed trajectory in advance, location-based services can notify users about the consequence of the movement. In summary, this thesis contains efficient algorithms that can be applied to diverse aspects of pervasive signals for mining human mobility. The new algorithms are aimed at problems in transition time detection, summarisation, and prediction. The solutions address the scalability issues and can work in big pervasive temporal and spatial data effectively and accurately.},
   
    author = {Sadri, Amin},
    keywords = {Pervasive signals;Spatio-temporal data;Trajectory prediction;Graph compression;Temporal segmentation;Time series analysis},
    language = {eng},
    school = {RMIT University},
    year = {2018},
   
}

Cite:

Related Publications

RUP: Large Room Utilisation Prediction with carbon dioxide sensor
Type : JournalArticle
Show More
A Scalable Room Occupancy Prediction with Transferable Time Series Decomposition of CO 2 Sensor Data
Type : JournalArticle
Show More
Topical Event Detection on Twitter
Type : ConferenceProceeding
Show More

© 2021 Flora Salim - CRUISE Research Group.