On computing temporal aggregates with range predicates

ABSTRACT

Computing temporal aggregates is an important but costly operation for applications that maintain time-evolving data (data warehouses, temporal databases, etc.) Due to the large volume of such data, performance improvements for temporal aggregate queries are critical. Previous approaches have aggregate predicates that involve only the time dimension. In this article we examine techniques to compute temporal aggregates that include key-range predicates as well (range-temporal aggregates). In particular we concentrate on the SUM aggregate, while COUNT is a special case. To handle arbitrary key ranges, previous methods would need to keep a separate index for every possible key range. We propose an approach based on a new index structure called the Multiversion SB-Tree, which incorporates features from both the SB-Tree and the Multiversion B+--tree, to handle arbitrary key-range temporal aggregate queries. We analyze the performance of our approach and present experimental results that show its efficiency. Furthermore, we address a novel and practical variation called functional range-temporal aggregates. Here, the value of any record is a function over time. The meaning of aggregates is altered such that the contribution of a record to the aggregate result is proportional to the size of the intersection between the record's time interval and the query time interval. Both analytical and experimental results show the efficiency of our result.

REFERENCES

• 1: Bruno Becker , Stephan Gschwind , Thomas Ohler , Bernhard Seeger , Peter Widmayer, An asymptotically optimal multiversion B-tree, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.264-275, December 1996 [doi>10.1007/s007780050028]
• 2: Bernard Chazelle, Functional approach to data structures and its use in multidimensional searching, SIAM Journal on Computing, v.17 n.3, p.427-462, June 1988 [doi>10.1137/0217026]
• 3: Dengfeng Gao , Jose Alvin G. Gendrano , Bongki Moon , Richard Thomas Snodgrass , Minseok Park , Bruce C. Huang , Jim M. Rodrigue, Main Memory-Based Algorithms for Efficient Parallel Aggregation for Temporal Databases, Distributed and Parallel Databases, v.16 n.2, p.123-163, September 2004 [doi>10.1023/B:DAPD.0000028553.70337.e1]
• 4: Bruce C. Huang, Parallel Algorithms for Computing Temporal Aggregates, Proceedings of the 15th International Conference on Data Engineering, p.418, March 23-26, 1999
• 5: Sathish Govindarajan , Pankaj K. Agarwal , Lars Arge, CRB-Tree: An Efficient Indexing Scheme for Range-Aggregate Queries, Proceedings of the 9th International Conference on Database Theory, p.143-157, January 08-10, 2003
• 6: Christian S. Jensen , Richard Thomas Snodgrass, Temporal Data Management, IEEE Transactions on Knowledge and Data Engineering, v.11 n.1, p.36-44, January 1999 [doi>10.1109/69.755613]
• 7: Sung Tak Kang , Yon Dohn Chung , Myoung Ho Kim, An efficient method for temporal aggregation with range-condition attributes, Information Sciences—Informatics and Computer Science: An International Journal, v.168 n.1-4, p.243-265, 3 December 2004 [doi>10.1016/j.ins.2004.02.024]
• 8: Jong Soo Kim , Sung Tak Kang , Myoung-Ho Kim, Effective Temporal Aggregation Using Point-Based Trees, Proceedings of the 10th International Conference on Database and Expert Systems Applications, p.1018-1030, August 30-September 03, 1999
• 9: Nick Kline , Richard Thomas Snodgrass, Computing Temporal Aggregates, Proceedings of the Eleventh International Conference on Data Engineering, p.222-231, March 06-10, 1995
• 10: Kline, N. and Soo, M. 1998. Time-IT, the time-integrated testbed. ftp://ftp.cs.arizona.edu/timecenter/time-it-0.1.tar.gz.
• 11: Ines Fernando Vega Lopez, Scalable Algorithms for Large Temporal Aggregation, Proceedings of the 16th International Conference on Data Engineering, p.145, February 28-March 03, 2000
• 12: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 13: Betty Salzberg , Vassilis J. Tsotras, Comparison of access methods for time-evolving data, ACM Computing Surveys (CSUR), v.31 n.2, p.158-221, June 1999 [doi>10.1145/319806.319816]
• 14: Yufei Tao , Dimitris Papadias, Range Aggregate Processing in Spatial Databases, IEEE Transactions on Knowledge and Data Engineering, v.16 n.12, p.1555-1570, December 2004 [doi>10.1109/TKDE.2004.93]
• 15: Yufei Tao , Dimitris Papadias , Christos Faloutsos, Approximate Temporal Aggregation, Proceedings of the 20th International Conference on Data Engineering, p.190, March 30-April 02, 2004
• 16: Yufei Tao , Xiaokui Xiao, Efficient temporal counting with bounded error, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.1271-1292, August 2008 [doi>10.1007/s00778-007-0066-x]
• 17: Jun Yang , Jennifer Widom, Incremental Computation and Maintenance of Temporal Aggregates, Proceedings of the 17th International Conference on Data Engineering, p.51-60, April 02-06, 2001
• 18: Yang, J. and Widom, J. 2003. Incremental computation and maintenance of temporal aggregates. In Proceedings of the International Conference on Very Large Data Bases (VLDB) 12, 3, 262--283.
• 19: Ye, X. and Keane, J. 1997. Processing temporal aggregates in parallel. In Proceedings of the International Conference on Systems, Man, and Cybernetics. 1373--1378.
• 20: Donhui Zhang , Alexander Markowetz , Vassilis Tsotras , Dimitrios Gunopulos , Bernhard Seeger, Efficient computation of temporal aggregates with range predicates, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.237-245, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375600]
• 21: Donghui Zhang , Vassilis J. Tsotras , Dimitrios Gunopulos, Efficient aggregation over objects with extent, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543629]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.0 General

General Terms:
Algorithms

Keywords:
Temporal aggregates, functional aggregates, indexing, range predicates