In spatial data processing, for example in GISs where each map constitutes a specific thematic layer with its own non-overlapping categories, the need for fast retrieval of all or some of the categories that exist in a given region is emerged. In simple words, searching for a category is deduced to searching for the specific color with which this category is represented in the map. The efficient processing of queries which are based both on the feature as well as on the spatial object location is pursued.
Assume a user query for information from a thematic map of size that contains non-overlapping features, where = and is a positive integer. Since thematic maps contain more than one feature, the regular space decomposition process will stop when a homogeneous block, i.e. a maximal block that is fully covered by one feature only, is reached. As already seen in the previous examples, for the sake of uniformity the image background is treated as a separate feature.