next up previous
Next: PERFORMANCE EVALUATION Up: Algorithm Description Previous: The Report Query

The Select Query

The last window query is the selection query where the user asks for the blocks of the map in the queried window where the wanted features are found. As in the case of the exist query, for each maximal block searching starts by examining the entries at B$^+$tree root. As already described, only the branches where the respective entry's bitstring has at least one position of the queried features set to 1, are followed. Once the leaf level is reached, then the queried maximal block is searched. As described in the previous subsection, if this searching is not successful, then we first try to see if its descendants exist in the tree. In such a case, only those descendants that are homogeneous with respect to one of the queried features are returned. If the descendants are not stored in the tree, then we have to look for its ancestor. Only then, it can be verified whether the ancestor is covered by one of the queried features or not. This procedure operates in exactly the same way as in the HL-tree, since we need to report the exact blocks where the features exist and in this case searching cannot be avoided with the use of the quadtree's internal nodes.


next up previous
Next: PERFORMANCE EVALUATION Up: Algorithm Description Previous: The Report Query
Eleni Tousidou
2000-01-03