Time and Space Efficient Secondary Memory Representation of Quadtrees

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 n × n in a feature space (e.g., an image) of size T × T using the hybrid linear quadtree stored on a B+-tree with bucket size r, the exist and report query can be answered with O(n logrT) accesses to secondary storage, while the select query can be answered with $O(n \log_r T+ n^2/r)$ accesses to secondary storage. This is an improvement in worst-case I/O time complexity over previous results 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 a low space occupancy overhead with respect to the classic linear quadtree.