Towards the universal spatial data model based indexing and its implementation in MySQL

Evangelos Katsikaros

AbstractThis thesis deals with spatial indexing and models that are able to abstract the variety of existing spatial index solutions. This research involves a thorough presentation of existing dynamic spatial indexes based on R-trees, investigating abstraction models and implementing such a model in MySQL.
To that end, the relevant theory is presented. A thorough study is performed on the recent and seminal works on spatial index trees and we describe their basic properties and the way search, deletion and insertion are performed on them. During this e ffort, we encountered details that baffled us, did not make the understanding the core concepts smooth or we thought that could be a source of confusion. We took great care in explaining in depth these details so that the current study can be a useful guide for a number of them.
A selection of these models were later implemented in MySQL. We investigated the way spatial indexing is currently engineered in MySQL and we reveal how search, deletion and insertion are performed. This paves the path to the understanding of our intervention and additions to MySQL's codebase. All of the code produced throughout this research was included in a patch against the RDBMS MariaDB.
TypeMaster's thesis [Academic thesis]
PublisherTechnical University of Denmark, DTU Informatics, E-mail:
AddressAsmussens Alle, Building 305, DK-2800 Kgs. Lyngby, Denmark
NoteSupervised by Associate Professor Francois Anton, DTU Informatics
Electronic version(s)[pdf]
Publication link
BibTeX data [bibtex]
IMM Group(s)Image Analysis & Computer Graphics