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

Gordevicius, Juozas; Gamper, Johann; Böhlen, Michael Hanspeter (2009). Parsimonious temporal aggregation. In: EDBT/ICDT 2009 Joint Conference, St. Petersburg, Russia, 23 March 2009 - 26 March 2009, 1006-1017.

Published Version


Temporal aggregation is a crucial operator in temporal databases and has been studied in various flavors, including instant temporal aggregation (ITA) and span temporal aggregation (STA), each having its strengths and weaknesses. In this paper we define a new temporal aggregation operator, called parsimonious temporal aggregation (PTA), which comprises two main steps: (i) it computes the ITA result over the input relation and (ii) it compresses this intermediate result to a user-specified size c by merging adjacent tuples and keeping the induced total error minimal; the compressed ITA result is returned as the final result. By considering the distribution of the input data and allowing to control the result size, PTA combines the best features of ITA and STA. We provide two evaluation algorithms for PTA queries. First, the oPTA algorithm computes an exact solution, by applying dynamic programming to explore all possibilities to compress the ITA result and selecting the compression with the minimal total error. It runs in O(n2pc) time and O(n2) space, where n is the size of the input relation and p is the number of aggregation functions in the query. Second, the more efficient gPTA algorithm computes an approximate solution by greedily merging the most similar ITA result tuples, which, however, does not guarantee a compression with a minimal total error. gPTA intermingles the two steps of PTA and avoids large intermediate results. The compression step of gPTA runs in O(np log(c + ?)) time and O(c + ?) space, where ? is a small buffer for ""look ahead"". An empirical evaluation shows good results: considerable reductions of the result size introduce only small errors, and gPTA scales to large data sets and is only slightly worse than the exact solution of PTA.



49 downloads since deposited on 01 Jun 2012
16 downloads since 12 months

Detailed statistics

Additional indexing

Item Type:Conference or Workshop Item (Paper), refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Event End Date:26 March 2009
Deposited On:01 Jun 2012 16:04
Last Modified:05 Apr 2016 15:26
Official URL:http://www.edbt.org/Proceedings/2009-StPetersburg/edbt/papers/p1006-Gordevicius.pdf
Related URLs:http://www.zora.uzh.ch/65048/
Other Identification Number:merlin-id:2293

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

Repository Staff Only: item control page