Browsing by Subject "predictive indexing"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    PIMMLI: Predictive In-Memory Multi-Level Indexing for Distributed Trajectory Streams
    (2021-05) Samad, Abdul
    The popularity of location-based social media and GPS-enabled mobile devices has produced a large amount of streaming trajectory data. Each streaming trajectory consists of the sequence of positions that a moving object occupies in time and is generated in an online fashion, coming at high speed. Disciplines such as social networking, urban planning, ecology, and epidemiology have great interest in querying this type of data. However, the large volume of streaming trajectories poses scalability challenges that can be addressed by efficient indexing structures and in-memory distributed architectures such as Spark. Despite this, no streaming trajectory query processing algorithm has been proposed that uses indices and distributed architectures to tackle this large-scale problem. To address this, we propose a novel in-memory predictive multi-level indexing technique, called PIMMLI, that leverages the distributed Spark Streaming framework to process spatio-temporal queries on streaming trajectories in an efficient manner. We evaluated the effectiveness of PIMMLI on 3 real-life large-scale datasets. These experiments showed that PIMMLI had an average improvement of 3.5X in total query execution and indexing time over DITA, an existing state-of-the-art batch processing algorithm for spatio-temporal querying on trajectories, and of 34.09X in query execution time over an approach that uses no indices.
  • Thumbnail Image
    Item
    Predictive In-memory Multi-Level Indexing Algorithm for Spatiotemporal Trajectory Streams in Distributed Environments
    (2024-06) Phung, Thanh Nam
    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.