next up previous
Next: Window Queries Up: Algorithm Description Previous: Algorithm Description

The Creation Algorithm

The first step to build the proposed structure (either BSL-trees or BHL-trees) is the image decomposition, which will result in a list of maximal blocks. In the case of BSL-trees, this list will contain only homogeneous blocks, while in the case of the BHL-tree this list will also contain the internal quadtree nodes, that is the non-homogeneous blocks. Each entry in the list will consist of the locational code of the represented quadrant followed by the bitstring standing for the feature(s) that is(are) found in this quadrant. All entries of this list will be inserted in a B$^+$tree and will be stored at its leaves.

A bottom-up procedure is then followed to post the feature information of the stored quadrants to the upper B$^+$tree levels; i.e. a bitstring for each entry in all B$^+$tree nodes is extracted. At the leaf level this bitstring is identical to the original (in the sense of HL-trees) bitstring that was generated in the quadtree list. For the internal B$^+$tree levels though, the superimposition method (OR-ing) is used to propagate the feature information to higher tree levels. Thus, by superimposing the bitstrings which exist in a node, a new second-order bitstring is produced and stored in the entry that is the ancestor of this node at the next higher level. This procedure propagates upwards until the root is reached.


next up previous
Next: Window Queries Up: Algorithm Description Previous: Algorithm Description
Eleni Tousidou
2000-01-03