Abstract
Many applications of spatio-temporal databases require support for sequenced spatio-temporal (SST) aggregation, e.g., when analyzing traffic density in a city. Conceptually, an SST aggregation produces one aggregate value for each point in time and space.
This paper is the first to propose a method to efficiently evaluate SST aggregation queries for the COUNT, SUM, and AVG aggregation functions. Based on a discrete time model and a discrete, 1.5 dimensional space model that represents a road network, we generalize the concept of (temporal) constant intervals towards constant rectangles that represent maximal rectangles in the space-time domain over which the aggregation result is constant. We propose a new data structure, termed SST-tree, which extends the Balanced Tree for one-dimensional temporal aggregation towards the support for two-dimensional, spatio-temporal aggregation. The main feature of the Balanced Tree to store constant intervals in a compact way by using two counters is extended towards a compact representation of constant rectangles in the space-time domain. We propose and evaluate two variants of the SST-tree. The SSTT-tree and SSTH-tree use trees and hashmaps to manage spacestamps, respectively. Our experiments show that both solutions outperform a brute force approach in terms of memory and time. The SSTH-tree is more efficient in terms of memory, whereas the SSTT-tree is more efficient in terms of time.