Towards ml-enhanced trajectory query processing
File(s)
Author(s)
Yang, Guang
Type
Thesis
Abstract
The rapid growth in location-based services has generated massive trajectory data. Centralized databases have faltered under the demands of low-latency services and stringent privacy regulations. Addressing scalability and flexibility challenges for large-scale trajectory data management necessitates research on optimized index structures.
In this thesis, we propose a modular approach using hybrid indexing to tackle the two challenges from two levels: (1) Global scalability point of view (across machines) and (2) Local efficiency point of view (within each machine). Together, these two levels form a comprehensive view of the modular approach to enable efficient complex trajectory data processing. Specifically, we introduce the concept of machine learning (\acrshort{ml})-enhanced indexes or learned indexes into trajectory indexing. However, directly applying learned indexes introduces challenges since they cannot preserve the continuity of trajectories or cope with the dynamic nature of trajectories (requiring continuous updates).
From our insight into trajectory update patterns, where spatial updates shift the data locations within a predefined region while the temporal dimension continuously grows and expires, we propose to optimize traditional indexing techniques to improve updates in spatial dimensions at the global level. This allows the data structure to be more robust to data distribution shifts. Learned index techniques are applied locally to enhance temporal filtering and continuous timestamp updates.
We present a comprehensive view of our design approach by showcasing solutions to trajectory problems with different requirements. Specifically, at the global level, we developed a distributed approach for efficiently answering distance joins while preserving trajectory continuity and a framework for in-network range queries leveraging sensor and data distribution to ensure privacy. We then optimize each machine by transforming the temporal component of trajectories as a stream indexing problem. Two updatable and parallelizable learned indexes were developed to handle the temporal streams under various query workloads and update characteristics.
In this thesis, we propose a modular approach using hybrid indexing to tackle the two challenges from two levels: (1) Global scalability point of view (across machines) and (2) Local efficiency point of view (within each machine). Together, these two levels form a comprehensive view of the modular approach to enable efficient complex trajectory data processing. Specifically, we introduce the concept of machine learning (\acrshort{ml})-enhanced indexes or learned indexes into trajectory indexing. However, directly applying learned indexes introduces challenges since they cannot preserve the continuity of trajectories or cope with the dynamic nature of trajectories (requiring continuous updates).
From our insight into trajectory update patterns, where spatial updates shift the data locations within a predefined region while the temporal dimension continuously grows and expires, we propose to optimize traditional indexing techniques to improve updates in spatial dimensions at the global level. This allows the data structure to be more robust to data distribution shifts. Learned index techniques are applied locally to enhance temporal filtering and continuous timestamp updates.
We present a comprehensive view of our design approach by showcasing solutions to trajectory problems with different requirements. Specifically, at the global level, we developed a distributed approach for efficiently answering distance joins while preserving trajectory continuity and a framework for in-network range queries leveraging sensor and data distribution to ensure privacy. We then optimize each machine by transforming the temporal component of trajectories as a stream indexing problem. Two updatable and parallelizable learned indexes were developed to handle the temporal streams under various query workloads and update characteristics.
Version
Open Access
Date Issued
2024-04-11
Date Awarded
01/03/2025
License URL
Advisor
Heinis, Thomas
Publisher Department
Department of Computing
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)