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.
View at publisher
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 efﬁcient 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.
55 downloads since deposited on 09 Oct 2012
11 downloads since 12 months
|Item Type:||Journal Article, refereed, original work|
|Communities & Collections:||03 Faculty of Economics > Department of Informatics|
|Dewey Decimal Classification:||000 Computer science, knowledge & systems|
|Deposited On:||09 Oct 2012 13:36|
|Last Modified:||16 Dec 2013 16:59|
|ISSN:||1066-8888 (P) 0949-877X (E)|
|Free access at:||Related URL. An embargo period may apply.|
|Other Identification Number:||merlin-id:7323|
Users (please log in): suggest update or correction for this item
Repository Staff Only: item control page