Fully Dynamic Metric Access Methods based on Hyperplane Partitioning
Gonzalo Navarro and Roberto Uribe
Metric access methods based on hyperplane partitioning have the advantage,
compared to the ball-partitioning-based ones, that regions do not overlap.
The price is less flexibility for controlling the tree shape, especially
in the dynamic scenario, that is, upon insertions and deletions of objects.
In this paper we introduce a technique called ghost hyperplanes, which
enables fully dynamic data structures based on hyperplane partitioning.
We apply the technique to Brin's GNAT static index, obtaining a dynamic
variant called EGNAT, which in addition we adapt to secondary memory.
We show experimentally that the EGNAT is competitive with the
M-tree, the baseline for this scenario. We also apply the ghost
hyperplane technique to Voronoi trees, obtaining a competitive
dynamic structure for main memory.