Trajectory data simplification, similarity search and inference with deep learning
With the proliferation of GPS devices, trajectory data is being generated at an unprecedented speed, and the interest in the management and analysis of trajectory data has also grown dramatically. Trajectory data corresponds to a sequence of positions and timestamps to capture the traces of moving o...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis-Doctor of Philosophy |
| Language: | English |
| Published: |
Nanyang Technological University
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/164589 |
| _version_ | 1811684888675352576 |
|---|---|
| author | Wang, Zheng |
| author2 | Long Cheng |
| author_facet | Long Cheng Wang, Zheng |
| author_sort | Wang, Zheng |
| collection | NTU |
| description | With the proliferation of GPS devices, trajectory data is being generated at an unprecedented speed, and the interest in the management and analysis of trajectory data has also grown dramatically. Trajectory data corresponds to a sequence of positions and timestamps to capture the traces of moving objects such as vehicles, pedestrians, sports players, etc. It embeds rich spatial and temporal information of moving objects, and how to manage and analyze the data efficiently and effectively has attracted much research attention in recent years. In this thesis, we explore effective and efficient solutions for trajectory data simplification, similarity search, and inference with emerging deep learning techniques.
First, we study three trajectory simplification problems, i.e., (1) error-bounded trajectory simplification, (2) size-bounded trajectory simplification, and (3) query accuracy driven trajectory simplification. Trajectory simplification is a common practice in trajectory data pre-processing, which aims to drop some of the points in a trajectory to release the burden on trajectory transmission, storage, and query processing. To be specific, for (1) and (2), existing algorithms usually involve some decision making tasks (e.g., deciding which point to drop), for which, some human-crafted rules are used. Motivated by this, we propose to learn a policy for the decision making tasks via reinforcement learning (RL) and develop trajectory simplification methods based on the learned policy. Compared with existing algorithms, our RL-based methods are data-driven and can adapt to different dynamics underlying the problem. For (3), existing techniques rely mainly on hand-craft error measures when deciding which point to drop when simplifying a trajectory. While the hope may be that such simplification affects the subsequent usability of the data only minimally, the usability of the simplified data remains largely unexplored. Instead of using error measures that indirectly may to some extent yield simplified trajectories with high usability, we propose a direct approach to simplification and present the first study of query accuracy driven trajectory simplification, where the direct objective is to achieve a simplified trajectory database that preserves the query accuracy of the original database as much as possible.
Second, we study two similarity search problems, namely (1) subtrajectory similarity search (SimSub) and (2) multi-trajectory similarity search. The two problems are variants of the similar trajectory search problem, which is a fundamental problem of trajectory management, and have many applications such as those that take subtrajectories and/or groups of trajectories as basic units for analysis (e.g., sports play analytics). To be specific, for (1), we develop a suite of algorithms including both exact and approximate ones. Among those approximate algorithms, two that are based on deep reinforcement learning stand out and outperform those non-learning based algorithms in terms of effectiveness and efficiency. For (2), we propose a deep learning approach to learn the representations of sports plays, called play2vec, which is robust against noise and takes only linear time to compute the similarity between two sports plays. In addition, we extend the second problem to a database of games and a query play, the problem is to find those fragments of the games (i.e., plays), which are the most similar to the query play. This new problem setting is more aligned with real application scenarios, since the raw spatiotemporal sports data is collected in the units of games, but not plays.
Third, we study the problem of inferring user socioeconomic status based on their trajectories. For this task, we propose a novel learning framework incorporating a Deep Network and a Recurrent Network for user socioeconomic status inference, which extracts the features of the mobility records from three aspects, namely spatiality, temporality and activity. Compared with existing studies, we make the following contributions in this line of research. First, we study a novel problem of inferring users’ economic statuses based on their GPS mobility records. This problem is new and has practical applications in real life (e.g., risk assessment for car loan applications/managements). Second, we propose a novel analytical framework called DeepSEI for the problem, which is a supervised deep learning model and incorporates two neural networks to capture the features from three aspects of users’ mobility records.
In summary, the thesis aims at leveraging deep learning techniques for effective and efficient trajectory data simplification, similarity search and inference. |
| first_indexed | 2024-10-01T04:35:47Z |
| format | Thesis-Doctor of Philosophy |
| id | ntu-10356/164589 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:35:47Z |
| publishDate | 2023 |
| publisher | Nanyang Technological University |
| record_format | dspace |
| spelling | ntu-10356/1645892023-03-06T07:30:04Z Trajectory data simplification, similarity search and inference with deep learning Wang, Zheng Long Cheng School of Computer Science and Engineering c.long@ntu.edu.sg Engineering::Computer science and engineering::Information systems::Database management Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence With the proliferation of GPS devices, trajectory data is being generated at an unprecedented speed, and the interest in the management and analysis of trajectory data has also grown dramatically. Trajectory data corresponds to a sequence of positions and timestamps to capture the traces of moving objects such as vehicles, pedestrians, sports players, etc. It embeds rich spatial and temporal information of moving objects, and how to manage and analyze the data efficiently and effectively has attracted much research attention in recent years. In this thesis, we explore effective and efficient solutions for trajectory data simplification, similarity search, and inference with emerging deep learning techniques. First, we study three trajectory simplification problems, i.e., (1) error-bounded trajectory simplification, (2) size-bounded trajectory simplification, and (3) query accuracy driven trajectory simplification. Trajectory simplification is a common practice in trajectory data pre-processing, which aims to drop some of the points in a trajectory to release the burden on trajectory transmission, storage, and query processing. To be specific, for (1) and (2), existing algorithms usually involve some decision making tasks (e.g., deciding which point to drop), for which, some human-crafted rules are used. Motivated by this, we propose to learn a policy for the decision making tasks via reinforcement learning (RL) and develop trajectory simplification methods based on the learned policy. Compared with existing algorithms, our RL-based methods are data-driven and can adapt to different dynamics underlying the problem. For (3), existing techniques rely mainly on hand-craft error measures when deciding which point to drop when simplifying a trajectory. While the hope may be that such simplification affects the subsequent usability of the data only minimally, the usability of the simplified data remains largely unexplored. Instead of using error measures that indirectly may to some extent yield simplified trajectories with high usability, we propose a direct approach to simplification and present the first study of query accuracy driven trajectory simplification, where the direct objective is to achieve a simplified trajectory database that preserves the query accuracy of the original database as much as possible. Second, we study two similarity search problems, namely (1) subtrajectory similarity search (SimSub) and (2) multi-trajectory similarity search. The two problems are variants of the similar trajectory search problem, which is a fundamental problem of trajectory management, and have many applications such as those that take subtrajectories and/or groups of trajectories as basic units for analysis (e.g., sports play analytics). To be specific, for (1), we develop a suite of algorithms including both exact and approximate ones. Among those approximate algorithms, two that are based on deep reinforcement learning stand out and outperform those non-learning based algorithms in terms of effectiveness and efficiency. For (2), we propose a deep learning approach to learn the representations of sports plays, called play2vec, which is robust against noise and takes only linear time to compute the similarity between two sports plays. In addition, we extend the second problem to a database of games and a query play, the problem is to find those fragments of the games (i.e., plays), which are the most similar to the query play. This new problem setting is more aligned with real application scenarios, since the raw spatiotemporal sports data is collected in the units of games, but not plays. Third, we study the problem of inferring user socioeconomic status based on their trajectories. For this task, we propose a novel learning framework incorporating a Deep Network and a Recurrent Network for user socioeconomic status inference, which extracts the features of the mobility records from three aspects, namely spatiality, temporality and activity. Compared with existing studies, we make the following contributions in this line of research. First, we study a novel problem of inferring users’ economic statuses based on their GPS mobility records. This problem is new and has practical applications in real life (e.g., risk assessment for car loan applications/managements). Second, we propose a novel analytical framework called DeepSEI for the problem, which is a supervised deep learning model and incorporates two neural networks to capture the features from three aspects of users’ mobility records. In summary, the thesis aims at leveraging deep learning techniques for effective and efficient trajectory data simplification, similarity search and inference. Doctor of Philosophy 2023-02-06T06:42:40Z 2023-02-06T06:42:40Z 2023 Thesis-Doctor of Philosophy Wang, Z. (2023). Trajectory data simplification, similarity search and inference with deep learning. Doctoral thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/164589 https://hdl.handle.net/10356/164589 10.32657/10356/164589 en This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0). application/pdf Nanyang Technological University |
| spellingShingle | Engineering::Computer science and engineering::Information systems::Database management Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence Wang, Zheng Trajectory data simplification, similarity search and inference with deep learning |
| title | Trajectory data simplification, similarity search and inference with deep learning |
| title_full | Trajectory data simplification, similarity search and inference with deep learning |
| title_fullStr | Trajectory data simplification, similarity search and inference with deep learning |
| title_full_unstemmed | Trajectory data simplification, similarity search and inference with deep learning |
| title_short | Trajectory data simplification, similarity search and inference with deep learning |
| title_sort | trajectory data simplification similarity search and inference with deep learning |
| topic | Engineering::Computer science and engineering::Information systems::Database management Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence |
| url | https://hdl.handle.net/10356/164589 |
| work_keys_str_mv | AT wangzheng trajectorydatasimplificationsimilaritysearchandinferencewithdeeplearning |