Parsimonious temporal aggregation

ABSTRACT

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(n²pc) time and O(n²) 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.

REFERENCES

• 1: Klaus Berberich , Srikanta Bedathur , Thomas Neumann , Gerhard Weikum, A time machine for text search, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277831]
• 2: M. H. Böhlen, J. Gamper, and C. S. Jensen. Multi-dimensional aggregation for temporal data. In Proc. of EDBT, volume 3896 of LNCS, pages 257--275. Springer, 2006.
• 3: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 4: Juozas Gordevicius , Johann Gamper , Michael Böhlen, A Greedy Approach Towards Parsimonious Temporal Aggregation, Proceedings of the 2008 15th International Symposium on Temporal Representation and Reasoning, p.88-92, June 16-18, 2008 [doi>10.1109/TIME.2008.24]
• 5: H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Viswanath Poosala , Kenneth C. Sevcik , Torsten Suel, Optimal Histograms with Quality Guarantees, Proceedings of the 24rd International Conference on Very Large Data Bases, p.275-286, August 24-27, 1998
• 6: Eamonn J. Keogh , Selina Chu , David Hart , Michael J. Pazzani, An Online Algorithm for Segmenting Time Series, Proceedings of the 2001 IEEE International Conference on Data Mining, p.289-296, November 29-December 02, 2001
• 7: Nick Kline , Richard Thomas Snodgrass, Computing Temporal Aggregates, Proceedings of the Eleventh International Conference on Data Engineering, p.222-231, March 06-10, 1995
• 8: Bongki Moon , Ines Fernando Vega Lopez , Vijaykumar Immanuel, Efficient Algorithms for Large-Scale Temporal Aggregation, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.744-759, March 2003 [doi>10.1109/TKDE.2003.1198403]
• 9: S. B. Navathe , R. Ahmed, A temporal relational model and a query language, Information Sciences: an International Journal, v.49 n.1-3, p.147-175, Oct.-Dec. 1989 [doi>10.1016/0020-0255(89)90026-1]
• 10: Yunyao Qu , Changzhou Wang , X. Sean Wang, Supporting fast search in time series for movement patterns in multiple scales, Proceedings of the seventh international conference on Information and knowledge management, p.251-258, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288664]
• 11: Richard Thomas Snodgrass , S. Gomez , E. McKenzie, Aggregates in the Temporal Query Language TQuel, IEEE Transactions on Knowledge and Data Engineering, v.5 n.5, p.826-842, October 1993 [doi>10.1109/69.243512]
• 12: P. Tuma. Implementing historical aggregates in TempIS. Master's thesis, Wayne State University, Detroit, Michigan, 1992.
• 13: Ines Fernando Vega Lopez , Richard T. Snodgrass , Bongki Moon, Spatiotemporal Aggregate Computation: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.17 n.2, p.271-286, February 2005 [doi>10.1109/TKDE.2005.34]
• 14: Changzhou Wang , Xiaoyang Sean Wang, Supporting Content-Based Searches on Time Series via Approximation, Proceedings of the 12th International Conference on Scientific and Statistical Database Management, p.69, July 26-28, 2000 [doi>10.1109/SSDM.2000.869779]
• 15: F. Wang. Employee temporal data set. http://timecenter.cs.aau.dk/.
• 16: Jun Yang , Jennifer Widom, Incremental computation and maintenance of temporal aggregates, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.3, p.262-283, October 2003 [doi>10.1007/s00778-003-0107-z]