Space Overhead

In the first set of experiments the space overhead involved in each method was measured. As explained in Section 3.1, no space overhead due to the use of the bitstring in the B$^+$tree nodes for the BSL-tree and the BHL-tree was considered. As a result, both SL and BSL nodes on one hand, and HL and BHL nodes on the other hand will have exactly the same number of entries for a given page size. This is the reason why in the experiments performed measuring the space overhead, only the three columns of the IL-trees, the BSL-trees and the BHL-trees are shown. The column of the SL-tree would be exactly the same to that of the BSL-tree, as the column of the HL-tree would be exactly the same to that of the BHL-tree.

Figure: Space Overhead involved in five different 512$\times$512 images containing 64 features.

As can be seen in Figure , the (B)HL-tree is the worst method regarding the space overhead, due to the storage of internal quadtree nodes in the B$^+$tree leaves and upwards. The space occupied by the IL-trees was found by summing up the space size occupied for each one of the feature-indices involved, i.e. the 64 indices of our experiment. It is also noticed that the (B)SL-trees are almost always the best ones, whereas the IL-trees are close with respect to the storage overhead.