The original Linear quadtree was firstly proposed for black and white images,
where the only information stored were the addresses of black quadrants
[5].
This means that the structure worked fine for window queries, since no
feature filtering was necessary, whereas the only expectation was the good
performance of the B
tree when queried with the spatial location of
objects based on the locational quadtree codes.
The next step towards the adjustment of the original method to the
efficient manipulation of multiple features (i.e. thematic maps) was
confined to the maintenance of feature information in the quadtree leaves.
As already seen, the bottom line in all previous methods is that this
information will be stored in the Btree leaves making it impossible to
take further advantage of the features as a spatial filter.
For example, though the HL-tree retains information for internal and
external quadtree nodes, both of them are stored only at the Btree leaf
level.
Consequently, we cannot take advantage of it in higher Btree levels to
avoid traversing some branches for queries based on feature information.
In the IL-trees, there is no need for filtering but instead several indexes
have to be traversed to answer queries involving multiple features.
In the present paper, a method aiming at achieving better exploitation of feature information in combination with spatial location is proposed. This is not always trivial since feature information and spatial location are two orthogonal issues that have no relation with each other.