Abstract
dc:description.abstractIndexes for multidimensional data based on the R-Tree are popularly used by databases for a wide range of applications. Such index trees support point and range queries but are costly to construct over datasets of millions of points. We present the Non-Intersecting R-Tree (NIR-Tree), a novel insert-efficient, in-memory, multidimensional index that uses bounding polygons to provide twice as efficient point queries, and equivalent range query performance while indexing data up to an order of magnitude faster. The NIR-Tree leverages non-intersecting bounding polygons to reduce the number of nodes accessed during queries, compared to existing R-family indexes. Our experiments demonstrate that inserting into a NIR-Tree is 27x faster than the ubiquitous R*-Tree, and 1.2x faster than the Revised R*-Tree. Furthermore, point queries in the NIR-Tree complete 2.2x faster than in the R*-Tree, and 3.1x faster than in the Revised R*-Tree, while range queries execute just as quickly.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2021
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Langendoen, Kyle Jacob
- Advisor dc:contributor.advisor
-
- Daudjee, Khuzaima
Subjects
dc:subject × 9Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/16972