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. 373  (Previous )


Nardelli E., Proietti G.

A time and space competitive pointerless representation of quadtrees

ABSTRACT
Efficient management of spatial data is becoming more and more important and for very large sets of 2-dimensional data, secondary memory data representations are required. An important class of queries for spatial data are those that extract a subset of the data: they are called window queries (also region or range queries). In this paper we propose and analyze a new data structure, namely the hybrid linear quadtree, for the efficient secondary memory processing of three kinds of window queries, that is the exist, the report and the select query. In particular we prove that for a window of size nxn in a feature space (e.g., an image) of size TxT (e.g., pixel elements) using the hybrid linear quadtree stored on a B-tree with bucket size r, the exist and report query can be answered with O(nlog_r T) accesses to secondary storage, while the select query can be answered with O(nlogr T+n ? /r) accesses to secondary storage. This is an improvement in worst-case time complexity over previous results [Nar93a] and shows that multiple non-overlapping features (i.e., coloured images) can be treated with the same I/O complexity as single features (i.e., black and white images). Furthermore, we show that the hybrid linear quadtree has an average space occupancy infinitesimal with respect to the secondary memory version of the incomplete pyramid data structure for a very large class of images described by various probabilistic models proposed in the literature.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -