Efficient Secondary Memory Processing of Window Queries on Spatial Data

Efficient management of spatial data is becoming more and more important, requiring very large spatial database secondary memory data representations. 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 queries. In particular, we show that for the three queries, both for single feature and for multiple non-overlapping features, the number of accesses is never greater than the number of pixels inside the window. More precisely, we prove that for a window of size n × n in a feature space (e.g., an image) of size T × T (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 generic images can be answered with O(nlogrT + n2/r) accesses on secondary storage. We also show that for two-dimensional range searching where output size is proportional to the search space size, the proposed data structure is optimal against other data structures proposed in the literature.