next up previous
Next: PROPOSED METHOD Up: RELATED WORK AND MOTIVATION Previous: Independent Linear Quadtrees

Query Manipulation and Motivation

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 B$^+$tree 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 B$^+$tree leaf level. Consequently, we cannot take advantage of it in higher B$^+$tree 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.


next up previous
Next: PROPOSED METHOD Up: RELATED WORK AND MOTIVATION Previous: Independent Linear Quadtrees
Eleni Tousidou
2000-01-03