MOF-TREE - A SPATIAL ACCESS METHOD TO MANIPULATE MULTIPLE OVERLAPPINGFEATURES

In this paper we investigate the manipulation df large sets of 2-dimen sional data representing multiple overlapping features (e.g. semantica lly distinct overlays of a given region), and we present a new access method, the MOF-tree. We perform an analysis with respect to the stora ge requirements and a time analysis with respect to window query opera tions involving multiple features (e.g. to verify if a constraint defi ned on multiple overlays holds or not inside a certain region). We exa mine both the pointer-based as well as the pointerless MOF-tree repres entations, using as space complexity measure the number of bits used i n main memory and the number of disk pages in secondary storage respec tively. In particular, we show that the new structure is space competi tive in the average case, both in the pointer version and in the linea r version, with respect to multiple instances of a region quadtree and a linear quadtree respectively, where each instance represents a sing le feature. Concerning the time performance of the new structure, we a nalyze the class of window (range) queries, posed on the secondary mem ory implementation. We show that the I/O worst-case time complexity fo r processing a number of window queries in the given image space, is c ompetitive with respect to multiple instances of a linear quadtree, as confirmed by experimental results. Finally, we show that the MOF-tree can efficiently support spatial join processing in a spatial DBMS. (C ) 1997 Elsevier Science Ltd. All rights reserved.