Quick Search:

uzh logo
Browse by:

Zurich Open Repository and Archive

Maintenance: Tuesday, July the 26th 2016, 07:00-10:00

ZORA's new graphical user interface will be relaunched (For further infos watch out slideshow ZORA: Neues Look & Feel). There will be short interrupts on ZORA Service between 07:00am and 10:00 am. Please be patient.

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


3 citations in Web of Science®
4 citations in Scopus®
Google Scholar™



66 downloads since deposited on 09 Oct 2012
14 downloads since 12 months

Detailed statistics

Additional indexing

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:05 Apr 2016 15:59
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

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

Repository Staff Only: item control page