Publications of Guido Proietti

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  1993, with author Proietti G., in the category IASI Research Reports (or show them all):


IASI Research Report n. 372  (Previous    Next)


Nardelli E., Proietti G.

Unity is strength or it is better to keep spatial data together

ABSTRACT
In this paper we analyze the case of efficiently storing and processing large sets of 2-dimensional data representing multiple overlapping features, that is semantically distinct overlays in a given region, such as lakes, rivers, cities and roads inside a geographical map. We present a new data structure, namely the MOF-tree, to adress this issue. We show that several advantages derive from storing multiple features in the MOF-tree, from the standpoint of saving space and execution time in a large class of operation involving the multiple features as a whole (e.g., to verify if a constraint defined on multiple overlays holds or not inside a certain region). We focus both on pointer based and on poiterless representations of such a structure, using as space complexity measure the number of bits used in the RAM with uniform costs model. In particular, we show that the MOF-tree is in the average case space competitive, both in the pointer version and in the linear version, with respect to multiple instances of the quadtree data structure each representing a single feature. Concerning time performances measure, we analyze a class of operations of great interest when working with a large volume of spatial data, where secondary storage needs to be used, namely range or window queries. Then, our time complexity is the number of secondary storage accesses. We show that the worst-case time complexity for processing a number of queries on a window in the given image space, is competitive with respect to all the proposed approaches in the literature. Finally, we show that the MOF-tree can efficiently support spatial join processes in a spatial DBMS.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -