Sequenced, Spatio-Temporal Aggregation in Road Networks
Authors
- Igor Timko (Free University of Bolzano, Italy)
- Michael Boehlen (Free University of Bozen-Bolzano, Italy)
- Johann Gamper (Free University of Bozen-Bolzano, Italy)
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 SSTtree, 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 SSTtree. The SSTtreeT and SSTtreeH 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 SSTtreeH is more efficient in terms of memory, whereas the SSTtreeT is more efficient in terms of time.
Session
EDBT Research Session 2: Spatio-Temporal (Tuesday, March 24, 11:00—12:30)