Predictive In-memory Multi-Level Indexing Algorithm for Spatiotemporal Trajectory Streams in Distributed Environments

Abstract

Trajectory analysis has received significant contributions in recent years. With the rapid explosion of GPS-enabled devices, several large-scale datasets have been created, e.g., the Geolife GPS dataset (17,621 trajectories) and the bdd100k dataset (100,000 trajectories). This has provided enormous streaming spatiotemporal data, benefiting many real-world applications, e.g., urban planning, mapping services, and carpooling. These applications benefit from performing many types of search queries on spatial data, such as range query and join query. Despite the importance of these types of queries on streaming data, many systems do not support them. Many also fail to handle the scalability and efficiency problems when the input data is too large. This thesis proposes the first predictive in-memory multi-level indexing algorithm called PIMMLI. We introduced predictive indexing to enhance the scalability of the indexing process and compared it against an existing state-of-the-art algorithm called DITA. We have conducted extensive experiments on real-world streaming datasets and compared the performance of PIMMLI against DITA on different hyperparameters. Our results show that PIMMLI (1) has a similar range query performance with DITA; (2) has at least a 5.8% improvement in join query performance compared to DITA; (3) has an average improvement of 28.10% for trajectory indexing.