MAMBO - Indexing Dead Space to Accelerate Spatial Queries✱
Giannis Evagorou, Thomas Heinis · 2021
With the increasing size and prevalence of spatial data across applications, efficiently indexing it becomes key. Minimum bounding boxes (MBBs) — i.e., axis-aligned rectangles that minimally enclose an object — used as approximations for complex geometric objects have become crucial for spatial indexes. MBBs succinctly summarize complex spatial objects and thus allow for an efficient filtering stage thanks to faster intersection tests. However, they introduce dead-space, i.e., space that is indexed but contains no spatial objects. Querying dead space gives no result but reads data from disk thus slowing down query execution unnecessarily.