  Geometric Near-neighbor Access Tree (GNAT) is a metric space indexing method
based on hierarchical hyperplane partitioning of the space. While GNAT is very
efficient in proximity searching, it has a bad reputation of being a memory
hog. We show that this is partially based on too coarse analysis, and that the
memory requirements can be lowered while at the same time improving the search
efficiency. We also show how to make GNAT memory adaptive in a smooth way, and
that the hyperplane partitioning can be replaced with ball partitioning, which
can further improve the search performance. We conclude with experimental
results showing the new methods can give significant performance boost.
