Master’s Thesis Presentation • Data Systems — A Non-Intersecting R-TreeExport this event to calendar

Tuesday, May 4, 2021 11:00 AM EDT

Please note: This master’s thesis presentation will be given online.

Kyle Langendoen, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Khuzaima Daudjee

Indexes 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.


To join this master’s thesis presentation on Zoom, please go to https://us02web.zoom.us/j/5198884567.

Location 
Online presentation
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
  1. 2024 (100)
    1. April (23)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)