CS MSc Thesis Presentation 12 December 2025

Friday, 12 December there will be a master thesis presentation in Computer Science at Lund University, Faculty of Engineering.

The presentation will take place in E:2116.

Note to potential opponents: Register as an opponent to the presentation of your choice by sending an email to the examiner for that presentation (firstname [dot] lastname [at] cs [dot] lth [dot] se). Do not forget to specify the presentation you register for! Note that the number of opponents may be limited (often to two), so you might be forced to choose another presentation if you register too late. Registrations are individual, just as the oppositions are! More instructions for opponents are found here on the LTH thesis project page.

13:15-14:00 in E:2116

• Presenters: Hanna Hertzberg, Alfred Andersson
• Title: Comparison of data structures for spatial databases
• Examiner: Flavius Gruian
• Supervisor: Jonas Skeppstedt (LTH), Tobias Leksell (Tactel)

This thesis compares the performance of three types of search trees---the point-region quadtree, the Guttman R-tree and the Hilbert packed R-tree. The goal was to find the fastest data structure when querying for points within a radius of a given point, and find the polygon a given point is situated inside of.

The results showed the Hilbert tree and quadtree to be performing equally fast when searching within a radius of a given point. The R-tree, on the other hand, performed poorly by being both the slowest and the most complicated to implement. For the polygon problem the quadtree was not used due to the structure's inability to handle polygons. Again the Hilbert tree outperformed the R-tree.

Evaluation was done by measuring the execution time of different operations on a POWER9 server. All code was written in C++.