The NOBH-tree: Improving in-memory metric access methods by using metric hyperplanes with non-overlapping nodes

In order to speed up similarity query evaluation, index structures divide the target dataset into subsets aimed at finding the answer without examining the entire dataset. As the complexity of the data types handled by modern applications keeps growing, searching by similarity becomes increasingly interesting, that makes the Metric Space Theory as the theoretical base to build the structures employed to index complex data. Also, as the main memory capacity grows and the price decreases, increasingly larger databases can be completely indexed in the main-memory. Thus, more and more applications require the data base management systems to quickly build indexes that can take advantage of memory-based indexes. In this paper, we propose a new family of metric access methods, called NOBH-trees that allow a non-overlapping division of the data space, combining Voronoi-shaped with ball-shaped regions to partition the metric space. We show how to query the subspaces divided by the hyperplanes and how the distance from any element to the hyperplane can be evaluated. The results obtained from the experiments show that the new MAM achieves better performance than the existing ones during both the construction and querying phases.