Improving query efficiency in high dimensional point indexes

Abstract

In this paper, we focus on the leaf level nodes of tree-like k-dimensional indexes that store the data entries, since those nodes represent the ajority of the nodes in the index. We propose a generic node splitting approach that defers splitting when possible and instead favors merging of a full node with an appropriate sibling and then re-splitting of the resulting node. Our experiments with the hB-tree, show that the proposed splitting approach achieves high average node storage utilization regardless of data distribution, data insertion patterns and dimensionality.