next up previous


Today, the manipulation of large volume two-dimensional data representing multiple features is of great interest for a variety of applications (e.g. in image databases, geographical information systems (GISs), scientific visualization, computer-aided design). So far, a number of different approaches have been presented to manipulate specific classes of spatial data (i.e. points, lines, rectangles, volumes and hyper-volumes), the most popular of which are quadtrees, bintrees [15], R-trees, the cell tree and the grid file. The interested reader can refer to [4,6,13] for interesting surveys on the topic.

The quadtree is a spatial access method based on the hierarchical image decomposition. Each image is regularly and successively decomposed into four quadrants until a homogeneous maximal block, with respect to the contained feature, is reached. Quadtrees can be implemented either in main memory or in secondary memory as pointer-based or pointerless structures, respectively. As far as secondary storage is concerned, two types of quadtree representations have been presented:

Since the need is on the random access of the quadtree leaves, the focus will be on the first representation.

In this work the focus is in the manipulation of raster thematic maps that contain multiple non-overlapping features, i.e. maps where each pixel contains one and only one feature and where pixels of the same color are aggregated into patches. For example, such thematic maps can be widely met in GISs. Such maps represent distinct thematic layers where each layer, as its name states, has a distinct theme (or subject). This theme could be the geology of the land, the elevation of the area, or the soil type found in the depicted area. For example, each type of soil occupies a certain space of the area and, apparently, no other type of soil can co-exist at the same space. This way, a map of non-overlapping categories is obtained. In the following, the words features, colors and categories will be used interchangeably.

Some of the most important types of queries applied to spatial data are window queries, since they allow extracting only the needed information from the whole image. More specifically, the window query types under examination are the following:

The efficient processing of window queries has already been studied by Nardelli and Proietti, who proposed adjusting region Linear quadtrees to manipulate the feature information [10]. The Hybrid Linear quadtree (HL-tree) was introduced as an enhancement to the previous method [11], whereas the MOF-tree, which was based on the HL-tree, was presented as a structure to efficiently manipulate images with multiple overlapping features [9]. Apart from these structures, Tanimoto and Pavlidis introduced a multi-resolution representation of images, the Pyramid data structure [14], two variations of which were later proposed by Aref and Samet [1], and Nardelli and Proietti [12]. Finally, in [7] a different in philosophy structure was presented, the S$^+$trees, which are based on DF-expressions. The latter structure basically manipulates black-and-white images and though it can be adjusted to manipulate multiple non-overlapping features, this would be performed in a less efficient way due to possible large space waste.

In this paper, a quadtree-based approach will be described and examined aiming to the efficient handling of thematic layers with multiple non-overlapping features. The focus will be on efficient processing of queries, which involve both the features and the spatial object locations as well. In the sequel, only the pointerless representation of this structure will be examined, although the same method could be also invariably applied to the pointer-based representation. By comparing the new structure to the previously proposed methods that were also based on Linear quadtrees, it will be shown that there is considerable gain achieved both in terms of storage space and time complexity.

The rest of the paper is organized as follows. In Section 2, some of the quadtree-based access methods that have already been presented in the past are reviewed. Also, the points which motivated in introducing the new method will be mentioned. In Section 3, the new structure will be described in detail, along with some new algorithms for the efficient performance of window queries. In Section 4, some representative results that were derived from the conducted experiments will be shown. Section 5 contains concluding remarks and some directions of possible future work.

next up previous
Eleni Tousidou