College of Engineering, Design & Computing Events

A Locality-Aware Indexing for Large-Scale Moving Object Trajectories on Cloud-Based Distributed Platforms
By Omar Saad M. Alqahtani

Wednesday, April 14, 2021
11:00 am MT

Doctoral Thesis Committee:
Dr. Tom Altman, Advisor
Dr. Gita Alaghband, Committee Chair
Dr. Ashis Kumer Biswas, Committee Member
Dr. Liang He, Committee Member
Dr. Michael Mannino, Committee Member

Abstract:

The availability of location-aware devices generates tremendous volumes of moving object trajectories. Cutting-edge cloud-based computing platforms, such as Apache Spark, are a typical solution for big spatial data and vast trajectory-driven applications. However, many challenges and obstacles have emerged concerning the adopted distributed platforms, the nature of the trajectories, the diversity in query types, and the enormous options of computing resources. This dissertation introduces three locality-aware indexing methods for large-scale trajectories. The first method is a proof-of-concept index that allows the end-user to control spatial and object localities. The second index can adapt to changes in distributed systems to satisfy a wide range of analytic applications and non-programmer end users. The adaptation capability is achieved by balancing the index structure between the spatial and object localities in order to control the parallelism capacity, the communication overhead, and the computation distribution. It is equipped with compulsory, discrete, and impact factor prediction models. The compulsory and discrete models are used to predict a locality pivot based on three fundamental aspects: computation resources, nature of the trajectories, and query types. The impact factor model is used to predict the influence of contrasting queries. The third index is able to adapt to the changes in a dynamic environment while maximizing the benefits of the available resources without any fine-tuning. It has innovative global and local indexes that implement several optimization approaches in order to contain the impact of balancing the locality pivot for real-time applications as well as analytic applications. In addition to these indexes, this dissertation provides efficient query processing algorithms for space-based, time-based, and object-based queries. The proposed approaches are evaluated using experimental studies that draw on four datasets to cover spatial, temporal, spatio-temporal, continuous, aggregation, and retrieval queries. In most cases, the experiments show a significant performance improvement compared to alternative indexing schemes and, more importantly, demonstrate the indexes’ adaptability across a range of environments.