Spatio-temporal aggregates over raster image data

ABSTRACT

Spatial, temporal and spatio-temporal aggregates over continuous streams of remotely sensed image data build a fundamental operation in many applications in the environmental sciences. Several approaches to efficiently compute multi-dimensional aggregates have been proposed in the literature. However, none of these approaches is suitable to compute aggregate values over streaming raster image data where the spatial extents and positions of individual images vary over time. In particular, the computation of a single aggregate value becomes less meaningful when the image data contribute only partially to a query region.

In this paper, we present an indexing scheme -- based on the Box-Aggregation Tree -- to efficiently compute spatio-temporal aggregates over streams of raster image data that vary in position and size. Using information about the spatial extent of incoming image data, we show how multiple aggregate values are computed for a single spatio-temporal query, thus providing more meaningful query results over spatially varying image data. Using National Oceanic and Atmospheric Administration's (NOAA) Geostationary Operational Environmental Satellite (GOES) data, we show the feasibility and efficiency of the proposed approach.

REFERENCES

• 1: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, 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.543615]
• 2: R. Bayer. Symmetric binary B-trees: Data structure and maintenance algorithms. Acta Informatica, 290--306, 1972.
• 3: D. Carney, U. Cetintemel, S. L. M. Cherniack, C. Convey, G. Seidman, M. Stonebraker, N.Tatbul, and S.Zdonik. Monitoring streams - A new class of data management applications. In Proceedings of the 28th International Conference on Very Large Data Bases, 215--226, Morgan Kaufmann, 2002.
• 4: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 5: Chuck Cranor , Theodore Johnson , Oliver Spataschek , Vladislav Shkapenyuk, Gigascope: a stream database for network applications, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872838]
• 6: Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843]
• 7: National Oceanic and Atmospheric Administration's (NOAA) Geostationary Operational Environmental Satellite (GOES). http://www.goes.noaa.gov
• 8: GeoStreams Project, University of California at Davis, Department of Computer Science. http://www.db.cs.ucdavis.edu/geostreams
• 9: J. Hellerstein, M. J. Franklin, S. Chandrasekaran, A. Deshpande, K. Hildrum, S. Madden, V. Raman, and M. A. Shah. Adaptive query processing: Technology in evolution. In IEEE Data Engineering Bulletin, 7--18, 2000.
• 10: I. F. V. Lopez, R. T. Snodgrass, and B. Moon. Spatiotemporal aggregate computation: A survey. A TimeCenter Technical Report, TR--77, January 2004. http://www.cs.auc.dk/research/DP/tdb/Time-Center/TimeCenterPublications/TR-77.pdf
• 11: Dimitris Papadias , Panos Kalnis , Jun Zhang , Yufei Tao, Efficient OLAP Operations in Spatial Data Warehouses, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.443-459, July 12-15, 2001
• 12: Indexing Spatio-Temporal Data Warehouses, Proceedings of the 18th International Conference on Data Engineering, p.166, February 26-March 01, 2002
• 13: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 14: Yufei Tao , George Kollios , Jeffrey Considine , Feifei Li , Dimitris Papadias, Spatio-Temporal Aggregation Using Sketches, Proceedings of the 20th International Conference on Data Engineering, p.214, March 30-April 02, 2004
• 15: Yufei Tao , Dimitris Papadias , Jun Zhang, Aggregate Processing of Planar Points, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.682-700, March 25-27, 2002
• 16: 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
• 17: Donghui Zhang , Dimitrios Gunopulos , Vassilis J. Tsotras , Bernhard Seeger, Temporal Aggregation over Data Streams Using Multiple Granularities, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.646-663, March 25-27, 2002
• 18: 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]
• 19: 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]
• 20: Donghui Zhang , Vassilis J. Tsotras, Improving min/max aggregation over spatial objects, Proceedings of the 9th ACM international symposium on Advances in geographic information systems, November 09-10, 2001, Atlanta, Georgia, USA [doi>10.1145/512161.512181]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Performance, Theory

Keywords:
indexing raster image data, spatio-temporal aggregates, streaming data