<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T11:48:49Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/21081" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/21081</identifier><datestamp>2025-03-26T23:35:37Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Daudjee, Khuzaima</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author">Chen, Ying</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2024-09-24T14:10:59Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2024-09-24T14:10:59Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2024-09-24</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2024-09-13</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/10012/21081</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract">This thesis introduces the Grid Minimum Bounding Box (GMB) as an enhancement to traditional Minimum Bounding Box (MBB), designed to mitigate the negative impact of dead space and improve query efficiency. The GMB achieves this by utilizing a low- cost grid bitmap to index dead space within the MBB, enabling the filtering of queries that intersect only with dead space. 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.
The key contributions of this thesis include the development of a data-driven algorithm for constructing GMBs, the design of a grid bitmap compression technique, the imple- mentation of an efficient maintenance system for dynamic GMBs, and the enhancement of search operations through GMB-based intersection tests. These contributions collectively establish GMB as a robust solution to the challenges presented by dead space within MBBs across different R-tree variants.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="title">Enhancing Spatial Query Efficiency Through Dead Space Indexing in Minimum Bounding Boxes</dim:field>
   <dim:field mdschema="dc" element="type">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department">David R. Cheriton School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline">Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree">Master of Mathematics</dim:field>
   <dim:field mdschema="uws-etd" element="embargo" qualifier="terms">0</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Daudjee, Khuzaima</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>