dc.contributor.author | Abubaker, Fadhil | |
dc.date.accessioned | 2024-01-23 20:03:58 (GMT) | |
dc.date.available | 2024-01-23 20:03:58 (GMT) | |
dc.date.issued | 2024-01-23 | |
dc.date.submitted | 2024-01-19 | |
dc.identifier.uri | http://hdl.handle.net/10012/20277 | |
dc.description.abstract | This thesis presents the NIR+-Tree, a disk-resident R-Tree variant that eliminates overlap among its minimum bounding rectangles (MBRs). The NIR+-Tree is an extension of the main-memory NIR-Tree, adopting techniques for efficient storage and retrieval on disk. By employing non-intersecting polygons instead of rectangles for data partitioning, the NIR+-Tree minimizes the number of spurious disk accesses incurred due to MBR overlap. To stabilize the height of the NIR+-Tree, the dynamically-sized polygons are stored in main-memory using an efficient encoding. Experimental results show that the NIR+-Tree is efficient at point queries and selective range queries, using 2× to 5× fewer disk accesses than its closest competitors, the R+-Tree and the R*-Tree.
Additionally, this thesis investigates bulk-loading algorithms for the NIR+-Tree. Bulk-loading can be used to efficiently construct an index from a pre-defined set of data. Bulk-loading algorithms that generate MBRs with significant overlap create NIR+-Trees with undesirable, complex polygons. This thesis shows that top-down bulk-loading algorithms are better suited for the NIR+-Tree than bottom-up algorithms, due to their overlap minimizing properties. These techniques enable the NIR+-Tree to be a complete, disk-based indexing solution for spatial data. | en |
dc.language.iso | en | en |
dc.publisher | University of Waterloo | en |
dc.title | Disk-based Indexing for NIR-Trees using Polygon Overlays | en |
dc.type | Master Thesis | en |
dc.pending | false | |
uws-etd.degree.department | David R. Cheriton School of Computer Science | en |
uws-etd.degree.discipline | Computer Science | en |
uws-etd.degree.grantor | University of Waterloo | en |
uws-etd.degree | Master of Mathematics | en |
uws-etd.embargo.terms | 0 | en |
uws.contributor.advisor | Daudjee, Khuzaima | |
uws.contributor.affiliation1 | Faculty of Mathematics | en |
uws.published.city | Waterloo | en |
uws.published.country | Canada | en |
uws.published.province | Ontario | en |
uws.typeOfResource | Text | en |
uws.peerReviewStatus | Unreviewed | en |
uws.scholarLevel | Graduate | en |