Meetup summary

2024-12-13 - Special topic - R-trees

Grigory led a special session on R-trees today.

Recommended reading:

• The Wikipedia article
• The original paper by Guttman (archived).

Agenda:

• Introduce R-trees (spatial data structure) and their motivating use cases.
• Walk through their implementation
• Analyze runtime and space requirements of the operations of interest
• Compare related data structures and discuss when you might prefer each.

Notes:

• We went through the motivations and use cases for R-trees.
• Sadly, these are not a panacea. In the worst case, performance can degrade to a superlinear runtime in the number of contained objects if you do not take special care to avoid pathologies. (At best, it’s hard to see how you could do better than $O(n)$ with pathological input where all items have the same bounds.)
• The insertion/split heuristics focus on minimizing differential volumes, which suggests that these work best when the input data (resident items) are unifomrly distributed through space. If you have very clumpy data, R-trees may underperform.
• Grigory’s C++ implementation for demonstration purposes. Note that “AABB” stands for “axis-aligned bounding box”, the primary atomic data structure that R-trees use to represent object bounding boxes.
• Good introductory lecture video on R-trees.