Quick Search:

uzh logo
Browse by:
bullet
bullet
bullet
bullet

Zurich Open Repository and Archive 

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.

[img]Published Version
PDF - Registered users only
775Kb

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.

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
Publisher:ACM
Publisher DOI:10.1145/1516360.1516368
Other Identification Number:merlin-id:2294
Citations:Google Scholar™

Users (please log in): suggest update or correction for this item

Repository Staff Only: item control page