Permanent URL to this publication: http://dx.doi.org/10.5167/uzh-56377
Timko, Igor; Böhlen, Michael H.; Gamper, Johann (2009). Sequenced spatio-temporal aggregation in road networks. In: EDBT '09: Proceedings of the 12th International Conference on Extending Database Technology, St. Petersburg, Russia, 24 March 2009 - 26 March 2009, 48-59.
PDF - Registered users only
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.
|Item Type:||Conference or Workshop Item (Paper), refereed, original work|
|Communities & Collections:||03 Faculty of Economics > Department of Informatics|
|DDC:||000 Computer science, knowledge & systems|
|Event End Date:||26 March 2009|
|Deposited On:||04 Jun 2012 13:39|
|Last Modified:||16 Oct 2012 19:37|
|Other Identification Number:||merlin-id:2294|
Users (please log in): suggest update or correction for this item
Repository Staff Only: item control page