PhD Defence – Leif Harald Karlsen

On November 20th, 2018, Leif Harald Karlsen defended his dissertation for the degree of Ph.D. The title of the dissertation was “A simple, General and Efficient Representation of Qualitative Spatial Information; An Approach Based on Bintrees”. The adjudication committee consisted of Professor Anthony Cohn (School of Computing, University of Leeds, UK), Professor Hanan Samet (Computer Science Department, University of Maryland, USA) and Professor Vera Hermine Goebel (Department of Informatics, University of Oslo). Leif Harald was supervised by Professor Martin Giese and Professor Arild Waaler. This worked looked at new ways in which computers can represent and search for spatial data in databases. The approach Leif Harald used was to translate complicated spatial objects into simpler structures, bintrees, in a way that the qualitative information in the data is maintained. This allows faster and better access to this data.

Spatial data is used in a great number of highly valuable applications, like route planning, automatic navigation and modelling of physical processes. However, on a computer, spatial data is often represented as complex numerical objects, and therefore requires advanced numerical algorithms to process. Despite this numerical complexity, we humans tend to think of spatial data in qualitative rather than quantitative terms. Motivated by this observation, Leif Harald’s work aims to improve the efficiency and applicability of answering queries involving qualitative relationships over spatial data. The novelty of the work is the development of an efficient algorithm that translates spatial objects into simpler structures, known as bintrees, in such a way that qualitative relationships are preserved. This simpler structure uses less storage space on disk compared to the original spatial data, and allows qualitative queries to be answered more efficiently. The thesis contains both a theoretical treatment of the problem based on logic, and implementation with experimental evaluation of the overall approach.