Please note: This master’s thesis presentation will take place in DC 2310.
Ying Chen Master’s candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Khuzaima Daudjee
This thesis introduces the Grid Minimum Bounding Box (GMB) as an enhancement to traditional MBBs, designed to mitigate the negative impact of deadspace in R-tree variants and improve query efficiency. The GMB achieves this by utilizing a low-cost bitmap to index deadspace within the MBB, enabling the filtering of queries that intersect only with deadspace. This filtering reduces false positives in intersection tests and minimizes unnecessary disk I/O to leaf nodes. A key advantage of GMB is that it is developed as an augmentation technique, enabling seamless integration with any R-tree variant without altering the core indexing architecture. The effectiveness of this technique is validated through a comprehensive set of experiments on both real-world and synthetic datasets, demonstrating significant improvements in query performance across various datasets and query types.