The raster model is widely used in Geographic Information Systems to represent data that vary continuously in space, such as temperatures, precipitations, elevation, among other spatial attributes. In applications like weather forecast systems, not just a single raster, but a sequence of rasters covering the same region at different timestamps, known as a raster time series, needs to be stored and queried. Compact data structures have proven successful to provide space-efficient representations of rasters with query capabilities. Hence, a naive approach to save space is to use such a representation for each raster in a time series. However, in this paper we show that it is possible to take advantage of the temporal locality that exists in a raster time series to reduce the space necessary to store it while keeping competitive query times for several types of queries.

The Hausdorff distance between two sets of points A and B corresponds to the largest of the distances between each object x ϵ A and its nearest neighbor in B. The Hausdorff distance has several applications, such as comparing medical images or comparing two transport routes. There are different algorithms to compute the Hausdorff distance, some operate with the sets of points in main memory and others in secondary memory. On the other hand, to face the challenge of indexing large sets of points in main memory, there are compact data structures such as k2-tree which, by minimizing storage, can be efficiently consulted. An efficient algorithm (HDK2) that allows the calculation of the Hausdorff distance in the compact structure k2-tree is presented in this article. This algorithm achieves an efficient solution in both time and space. Through a series of experiments, the performance of our algorithm was evaluated together with others proposed in literature under similar conditions. The results allow to conclude that HDK2 has a better performance in runtime than such algorithms.

In this work, we propose an efficient algorithm for retrieving K polygons of a vector dataset that overlap cells of a raster dataset, such that the K polygons are those overlapping the highest (or lowest) cell values among all polygons.

We present two compact representations of rasters, which are used in GIS to represent temperatures, elevations, and other spatial attributes, that support queries on the positions and/or the values stored. These representations are based on space-filling curves and recent advances on compact data structures. They are practical, competitive with recent works on the problem, and present some improved characteristics, such as a nice generalization to time series of rasters, i.e. the storage of several rasters covering the same area at different times.

k2-trees have been proved successful to represent in avery compact way different kinds of binary relations, such as web graphs, RDFs or raster data. In order to be a fully functional succinct representation for these domains, the k2-tree must support all the required operations for binary relations. In their original description, the authors include how to answer some of the most relevant queries over the k2-tree. In this paper, we extend this functionality and detail the algorithms to efficiently compute the k2-tree resulting from the union, intersection, difference or complement of binary relations represented using k2-trees.