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-65048

Gordevicius, Juozas; Gamper, Johann; Böhlen, Michael (2012). Parsimonious temporal aggregation. VLDB Journal, 21(3):309-332.

[img]
Preview
PDF
410kB

Abstract

Temporal aggregation is an important operationin temporal databases, and different variants thereof havebeen proposed. In this paper, we introduce a novel temporalaggregation operator, termed parsimonious temporal aggregation (PTA), that overcomes major limitations of existingapproaches. PTA takes the result of instant temporal aggregation (ITA) of size n, which might be up to twice as largeas the argument relation, and merges similar tuples untila given error () or size (c) bound is reached. The newoperator is data-adaptive and allows the user to control thetrade-off between the result size and the error introduced bymerging. For the precise evaluation of PTA queries, we propose two dynamic programming-based algorithms for sizeand error-bounded queries, respectively, with a worst-casecomplexity that is quadratic in n. We present two optimizations that take advantage of temporal gaps and differentaggregation groups and achieve a linear runtime in experiments with real-world data. For the quick computation ofan approximate PTA answer, we propose an efficient greedymerging strategy with a precision that is upper bounded byO(log n). We present two algorithms that implement thisstrategy and begin to merge as ITA tuples are produced. Theyrequire O(n log(c + β)) time and O(c + β) space, where βis the size of a read-ahead buffer and is typically very small. An empirical evaluation on real-world and synthetic datashows that PTA considerably reduces the size of the aggregation result, yet introducing only small errors. The greedyalgorithms are scalable for large data sets and introduce lesserror than other approximation techniques.

Item Type:Journal Article, refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
DDC:000 Computer science, knowledge & systems
Language:English
Date:2012
Deposited On:09 Oct 2012 13:36
Last Modified:16 Dec 2013 16:59
Publisher:Springer
ISSN:1066-8888 (P) 0949-877X (E)
Free access at:Related URL. An embargo period may apply.
Publisher DOI:10.1007/s00778-011-0243-9
Related URLs:http://www.zora.uzh.ch/56230/
Other Identification Number:merlin-id:7323
Citations:Web of Science®
Google Scholar™
Scopus®. Citation Count: 1

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

Repository Staff Only: item control page