Fully dynamic metric access methods based on hyperplane partitioning

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.

Research highlights
► We focus on metric access methods on secondary memory.
► We consider hyperplane partitioning methods, which have potential advantages compared to ball partitioning ones.
► We develop a method called “ghost hyperplane” to provide deletions in these methods.
► We compare the results with the alternatives and found our methods to be competitive.
► The ghost hyperplane method can be used in other scenarios as well.