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. 362  (Next)


Nardelli E., Proietti G.

Efficient secondary memory processing of window queries on spatial data

ABSTRACT
Efficient mamagement of spatial data is becoming more and more important and for very large spatial database secondary memory data representations are required. An important class of queries for spatial data are those which extract a subset of the data: they are called window queries. In this paper we analyze the efficient secondary memory processing of three kinds of window queries, namely the exist, the report and the select query. In particular we show that for all the above queries both for single feature and for multiple non-overlapping features the number of accesses is never greater than the number of pixel inside the window. More precisely, we prove that for a window of size nxn in a feature space (e.g., an image) of size TxT (e.g., pixel elements) the exist query for binary image can be answered with O(nlogrT) accesses on secondary storage, while in all the other cases, window queries on a generic images can be answered with O(nlogrT+n/r) accesses on secondary storage. We show also that for 2-dimensional range searching where output size is proportional to the search space size, our data structure is optimal against other data-structures proposed in the literature.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -