R-trees, an index structure for spatial data
During the first part of my studies it has been a requirement to take part in a so called proseminar. This is basically about doing some theoretical research on a given topic and finally presenting the result in a short lecture of about 45 minutes. Out of a list of proseminars offered at university, I have chosen “Algorithms and Data Structures for Database Systems” and furthermore have decided to work on the topic of R-trees.
R-trees are a data structure similar to binary trees but differ from them in the fact that they are designed to index spatial data. This is not necessarily limited to three-dimensional data. Just like binary trees do for one-dimensional datasets, R-trees provide efficient ways to perform INSERT, SEARCH and DELETE operations on their spatial content.
I don’t want to go into further detail here as both, the paper I wrote about this topic as well as the slides which I used during my presentation are available for download. So, feel free to have a look a those documents!
- Regulations and guidelines for proseminars [Website]