Spatiotemporal Aggregate Computation: A Survey
2005
1 INTRODUCTION
2 PRELIMINARIES
2.1 Aggregate Functions
2.2 Aggregation on Explicit Attributes
2.3 Aggregation on the Temporal and Spatial Extent
3 AGGREGATE FUNCTIONS ON EXPLICIT ATTRIBUTES
3.1 Formal Definition of Aggregation on Explicit Attributes
3.2 Existing Approaches for Evaluating Aggregate Queries
3.3 Aggregation and OLAP
4 TEMPORAL AGGREGATES
4.1 Formal Definition of Temporal Aggregation
4.2 Existing Approaches for Evaluating Temporal Aggregate Queries
4.2.1 Nonindexed Aggregation Evaluation
4.2.2 Indexed Aggregation Evaluation
4.3 Aggregates on Data Streams
5 SPATIAL AGGREGATION
5.1 Formal Definition of Spatial Aggregation
5.2 Existing Approaches for Evaluating Spatial Aggregate Queries
6 SPATIOTEMPORAL AGGREGATION
6.1 Formal Definition of Spatiotemporal Aggregation
6.2 Existing Approaches for Evaluating Spatiotemporal Aggregate Queries
7 RESEARCH OPPORTUNITIES
[1] D.J. Abadi, D. Carney, U. Cetintemel, M. Cherniack, C. Convey, S.
Lee, M. Stonebraker, N. Tatbul, and S. Zdonik, "Aurora: A New
Model and Architecture for Data Stream Management," VLDB J.,
vol. 12, no. 2, pp. 120-139, Aug. 2003.
[2] T. Abraham and J.F. Roddick, "Survey of Spatio-Temporal
Databases," GeoInformatica, vol. 3, no. 1, pp. 61-99, 1999.
[3] S. Agarwal, R. Agrawal, P.M. Deshpande, A. Gupta, J.F.
Naughton, R. Ramakrishnan, and S. Sarawagi, "On the Computation
of Multidimensional Aggregates," Proc. VLDB Conf., pp. 506-
521, Sept. 1996.
[4] B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom,
"Models and Issues in Data Stream Systems ," Proc. ACM
SIGACT-SIGMOD-SIGART Symp. Principles of Database Systems,
pp. 1-16, June 2002.
[5] J.L. Bentley, "Multidimensional Divide-and-Conquer," Comm.
ACM, vol. 23, no. 4, pp. 214-229, 1980.
[6] E. Bertino, B.C. Ooi, R. Sacks Davis, K.-L. Tan, J. Zobel, B.
Shidlovsky, and B. Catina, Indexing Techniques for Advanced
Database Systems. Boston: Kluwer Academic, 1997.
[7] C. Bettini, C.E. Dyreson, W.S. Evans, R.T. Snodgrass, and X.S.
Wang, "A Glossary of Time Granularity Concepts," Temporal
Databases: Research and Practice, pp. 406-413, Springer, 1998.
[8] C. Bettini, S. Jajodia, and S.X. Wang, Time Granularities in
Databases, Data Mining, and Temporal Reasoning. Berlin: Springer,
2000.
[9] L. Cabibbo and R. Torlone, "A Framework for the Investigation of
Aggregate Functions in Database Queries," Proc. Int'l Conf.
Database Theory (ICDT), pp. 383-397, Jan. 1999.
[10] S. Chaudhuri, G. Das, M. Datar, R. Motwani, and V. Narasayva,
"Overcoming Limitations of Sampling for Aggregation Queries,"
Proc. Int'l Conf. Data Eng., pp. 534-542, Apr. 2001.
[11] S. Chaudhuri, G. Das, and V. Narasayva, "A Robust, Optimization-
Based Approach for Approximate Answering of Aggregate
Queries," Proc. ACM-SIGMOD Conf., pp. 295-306, May 2001.
[12] C.X. Chen and C. Zaniolo, "SQLST : A Spatio-Temporal Data
Model and Query Language," Proc. Int'l Conf. Conceptual Modeling
(ER), pp. 96-111, Oct. 2000.
[13] Y.-J. Choi and C.-W. Chung, "Selectivity Estimation in Spatio-
Temporal Queries to Moving Objects," Proc. ACM-SIGMOD Conf.,
pp. 440-451, June 2002.
[14] S.-J. Chun, C.-W. Chung, J.-H. Lee, and S.-L. Lee, "Dynamic
Update Cube for Range-Sum Queries," Proc. VLDB Conf., pp. 521-
530, Sept. 2001.
[15] J. Considine, F. Li, G. Kollios, and J. Byers, "Approximate
Aggregation Techniques for Sensor Databases," Proc. Int'l Conf.
Data Eng., pp. 449-460, 2004.
[16] M. Datar, A. Gionis, P. Indyk, and R. Motwani, "Maintaining
Stream Statistics over Sliding Windows (Extended Abstract),"
Proc. Ann. ACM-SIAM Symp. Discrete Algorithms, pp. 635-644, Jan.
2002.
[17] A. Dobra, M. Garofalakis, J. Gehrke, and R. Rastogi, "Processing
Complex Aggregate Queries over Data Streams," Proc. ACMSIGMOD
Conf., pp. 61-72, June 2002.
[18] C.E. Dyreson, W.S. Evans, H. Lin, and R.T. Snodgrass, "Efficiently
Supporting Temporal Granularities," IEEE Trans. Knowledge and
Data Eng., vol. 12, no. 4, pp. 565-587, July/Aug. 2000.
[19] C.E. Dyreson, F. Grandi, W. Kafer, N. Kline, N. Lorentzos, Y.
Mitsopoulos, A. Montanari, D. Nonen, E. Peressi, B. Pernici, J.F.
Roddick, N.L. Sarda, M.R. Scalas, A. Segev, R.T. Snodgrass, M.D.
Soo, A. Tansel, P. Tiberio, G. Wiederhold, and C.S. Jensen, "A
Consensus Glossary of Temporal Database Concepts," SIGMOD
Record, vol. 23, no. 1, pp. 52-64, Mar. 1994
[20] R. Epstein, "Techniques for Processing of Aggregates in Relational
Database Systems," Technical Report UCB/ERL M7918, Univ. of
California, Berkeley, Feb. 1979.
[21] M. Erwing, R.H. Guting, M. Schneider, and M. Vazirgiannis,
"Spatio-Temporal Data Types: An Approach to Modeling and
Querying Moving Objects in Databases," GeoInformatica, vol. 3,
no. 3, pp. 269-296, 1999.
[22] L. Forlizzi, R.H. Guting, E. Nardelli, and M. Schneider, "A Data
Model and Data Structures for Moving Object Databases," Proc.
ACM-SIGMOD Conf., pp. 319-330, May 2000.
[23] J.C. Freytag and N. Goodman, "Translating Aggregate Queries
into Iterative Programs," Proc. VLDB Conf., pp. 138-146, Aug. 1986.
[24] V. Gaede and O. Gunther, "Multidimensional Access Methods,"
ACM Computing Surveys, vol. 30, no. 2, pp. 170-231, 1998.
[25] J.A.G. Gendrano, B.C. Huang, J.M. Rodrigue, B. Moon, and R.T.
Snodgrass, "Parallel Algorithms for Computing Temporal Aggregates,"
Proc. Int'l Conf. Data Eng., pp. 418-427, Mar. 1999.
[26] A.C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M.J. Strauss,
"Optimal and Approximate Computation of Summary Statistics
for Range Aggregates," Proc. ACM SIGACT-SIGMOD-SIGART
Symp. Principles of Database Systems, pp. 227-236, May 2001.
[27] A.C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M.J. Strauss,
"Surfing Wavelets on Streams: One-Pass Summaries for Approximate
Aggregate Queries," Proc. VLDB Conf., pp. 79-88, Sept. 2001.
[28] J. Gray, The Benchmark Handbook for Database and Transaction
Processing Systems. Morgan Kaufmann, 1991.
[29] J. Gray, S. Chaudhuri, A. Bosworth, A. Layman, D. Reichart, M.
Venkatrao, F. Pellow, and H. Pirahesh, "Data Cube: A Relational
Aggregation Operator Generalizing Group-by, Cross-Tab, and
Sub-Totals," Data Mining and Knowledge Discovery, vol. 1, no. 1,
pp. 29-53, 1997.
[30] S. Guha, N. Koudas, and K. Shim, "Data-Streams and Histograms,"
Proc. Ann. ACM Symp. Theory of Computing, pp. 471-475,
July 2001.
[31] P.J. Haas and J.M. Hellerstein, "Ripple Joins for Online Aggregation,"
Proc. ACM-SIGMOD Conf., pp. 287-298, June 1999.
[32] M. Hadjieleftheriou, G. Kollios, and V.J. Tsotras, "Efficient
Indexing of Spatiotemporal Objects," Proc. Conf. Extending
Database Technology, pp. 251-268, Mar. 2002.
[33] J.M. Hellerstein, P.J. Haas, and H.J. Wang, "Online Aggregation,"
Proc. ACM-SIGMOD Conf., pp. 171-182, May 1997.
[34] C.-T. Ho, R. Agrawal, N. Megiddo, and R. Srikant, "Range Queries
in OLAP Data Cubes," Proc. ACM-SIGMOD Conf., pp. 73-88, May
1997.
[35] M. Hogeweg, "Spatio-Temporal Visualization and the Need for
Integration," GeoInformatics, pp. 32-35, June 2001.
[36] C.S. Jensen and R.T. Snodgrass, "Semantics of Time-Varying
Information," Information Systems, vol. 21, no. 4, pp. 311-352, June
1996.
[37] C.O. Justice, D.K. Hall, and V.V. Salomonson, "The Moderate
Resolution Imaging Spectroradiometer (MODIS): Land Remote
Sensing for Global Change Research," IEEE Trans. Geoscience and
Remote Sensing, vol. 36, pp. 1228-1249, 1998.
[38] V. Khatri, S. Ram, R.T. Snodgrass, and G.M O'Brien, "Supporting
User-Defined Granularities and Indeterminacy in a Spatiotemporal
Conceptual Model," Annals Math. and Artificial Intelligence,
vol. 36, nos. 1-2, pp. 195-232, 2002.
[39] J.S. Kim, S.T. Kang, and M.-H. Kim, "On Temporal Aggregate
Processing Based on Time Points," Information Processing Letters,
vol. 71, nos. 5-6, pp. 213-220, Sept. 1999.
[40] N. Kline and R.T. Snodgrass, "Computing Temporal Aggregates,"
Proc. Int'l Conf. Data Eng., pp. 222-231, Mar. 1995.
[41] R.N. Kline, "Aggregation in Temporal Databases," PhD thesis,
Univ. of Arizona, May 1999.
[42] A. Klug, "Equivalence of Relational Algebra and Relational
Calculus Query Languages Having Aggregate Functions,"
J. ACM, vol. 29, no. 3, pp. 699-717, July 1982.
[43] Landsat, "Landsat Project Website," http://landsat7.usgs.gov/
index.php, Oct. 2003.
[44] P.-A. Larson, "Data Reduction by Partial Preaggregation," Proc.
Int'l Conf. Data Eng., pp. 706-715, 2002.
[45] I. Lazaridis and S. Mehrotra, "Progressive Approximate Aggregate
Queries with a Multi-Resolution Tree Structure," Proc. ACMSIGMOD
Conf., pp. 401-412, May 2001.
[46] J.A. Cotelo Lema and R.H. Guting, "Dual Grid: A New Approach
for Robust Spatial Algebra Implementation," GeoInformatica, vol. 6,
no. 1, pp. 57-76, 2002.
[47] N. Mamoulis and D. Papadias, "Selectivity Estimation of Complex
Spatial Queries," Proc. Int'l Symp. Advances in Spatial and Temporal
Databases, pp. 155-174, July 2001.
[48] U. Manber, Introduction to Algorithms: A Creative Approach. Reading,
Mass.: Addison-Wesley, 1989.
[49] Y. Manolopoulos, Y. Theodoridis, and V.J. Tsotras, Advanced
Database Indexing. Boston: Kluwer Academic, 2000.
[50] J. Melton, Advanced SQL:1999. Understanding Object-Relational and
Other Advanced Features. San Francisco: The Morgan Kaufman
Series in Data Management Systems, Morgan Kaufmann, 2003.
[51] MODIS, MODIS Web, http://modis.gsfc.nasa.gov/, Oct. 2003.
[52] B. Moon, I.F. Vega Lopez, and V. Immanuel, "Scalable Algorithms
for Large Temporal Aggregation," Proc. Int'l Conf. Data Eng.,
pp. 145-156, Mar. 2000.
[53] B. Moon, I.F. Vega Lopez, and V. Immanuel, "Efficient Algorithms
for Large-Scale Temporal Aggregation," IEEE Trans. Knowledge
and Data Eng., vol. 15, no. 3, pp. 744-751, May/June 2003.
[54] P. Ning, X.S. Wang, and S. Jajodia, "An Algebraic Representation
of Calendars," Annals Math. and Artificial Intelligence, vol. 36, nos. 1-
2, pp. 5-38, 2002.
[55] T. Palpanas, R. Sidle, R. Cochrane, and H. Pirahesh, "Incremental
Maintenance for Non-Distributive Aggregate Functions," Proc.
VLDB Conf., pp. 802-813, Aug. 2002.
[56] D. Papadias, P. Kalnis, J. Zhang, and Y. Tao, "Efficient OLAP
Operations in Spatial Data Warehouses," Proc. Int'l Symp.
Advances in Spatial and Temporal Databases, pp. 443-459, July 2001.
[57] D. Papadias, Y. Tao, P. Kalnis, and J. Zhang, "Indexing Spatio-
Temporal Data Warehouses," Proc. Int'l Conf. Data Eng., pp. 166-
175, 2002.
[58] C. Parent, S. Spaccapietra, and E. Zimanyi, "Spatio-Temporal
Conceptual Models: Data Structures + Space + Time," Proc. ACM
Int'l Symp. Advances in Geographic Information Systems (ACM-GIS),
pp. 26-33, Nov. 1999.
[59] T.B. Pedersen and N. Tryfona, "Pre-Aggregation in Spatial Data
Warehouses," Proc. Int'l Symp. Advances in Spatial and Temporal
Databases, pp. 460-480, July 2001.
[60] D. Pfoser and N. Tryfona, "Requirements, Definitions and
Notations for Spatiotemporal Application Environments," Proc.
ACM Int'l Symp. Advances in Geographic Information Systems (ACMGIS),
pp. 124-130, Nov. 1998.
[61] K. Porkaew, I. Lazaridis, and S. Mehrotra, "Querying Mobile
Objects in Spatio-Temporal Databases," Proc. Int'l Symp. Advances
in Spatial and Temporal Databases, pp. 59-78, July 2001.
[62] L. Qiao, D. Agrawal, and A. El Abbadi, "RHist: Adaptive
Summarization over Continuous Data Streams," Proc. ACM Int'l
Conf. Information and Knowledge Management (ACM-CIKM), pp. 469-
476, Nov. 2002.
[63] J.F. Roddick, K. Hornsby, and M. Spiliopoulou, "YABTSSTDMR—
Yet Another Bibliography of Temporal, Spatial, and Spatio-
Temporal Data Mining Research," Proc. SIGKDD Temporal Data
Mining Workshop, pp. 167-175, 2001.
[64] V.V. Salomonson, W.L. Barnes, P.W. Maymon, H.E. Montgomery,
and H. Ostrow, "MODIS: Advanced Facility Instrument for
Studies of the Earth as a System," IEEE Trans. Geoscience and
Remote Sensing, vol. 27, pp. 145-153, 1989.
[65] S. Saltenis and C.S. Jensen, "Indexing of Moving Objects for
Location- Based Services," Proc. Int'l Conf. Data Eng., pp. 463-472,
2002.
[66] B. Salzberg, "Access Methods," ACM Computing Surveys, vol. 28,
no. 1, pp. 117-120, 1996.
[67] T. Sellis, "Research Issues in Spatio-Temporal Database Systems,"
Proc. Int'l Symp. Advances in Spatial Databases, pp. 3-11, July 1999.
[68] R.T. Snodgrass, Developing Time-Oriented Database Applications in
SQL. San Francisco: Morgan Kaufmann, 2000.
[69] R.T. Snodgrass and I. Ahn, "A Taxonomy of Time in Databases,"
Proc. ACM-SIGMOD Conf., pp. 236-246, May 1985.
[70] R.T. Snodgrass, S. Gomez, and L.E. McKenzie Jr., "Aggregates in
the Temporal Query Language TQuel," IEEE Trans. Knowledge and
Data Eng., vol. 5, no. 5, pp. 826-842, Sept./Oct. 1993.
[71] J. Sun, D. Papadias, Y. Tao, and B. Liu, "Querying about the Past,
the Present, and the Future in Spatio-Temporal Databases," Proc.
Int'l Conf. Data Eng., pp. 202-213, 2004.
[72] Y. Tao, G. Kollios, J. Considine, F. Li, and D. Papadias, "Spatio-
Temporal Aggregation Using Sketches," Proc. Int'l Conf. Data Eng.,
pp. 214-226, 2004.
[73] Y. Tao and D. Papadias, "The MV3R-Tree: A Spatio-Temporal
Access Method for Timestamp and Interval Queries," Proc. VLDB
Conf., pp. 431-440, Sept. 2001.
[74] Y. Tao, D. Papadias, and C. Faloutsos, "Approximate Temporal
Aggregation," Proc. Int'l Conf. Data Eng., pp. 190-201, 2004.
[75] Y. Tao, D. Papadias, and J. Zhang, "Aggregate Processing of
Planar Points," Proc. Conf. Extending Database Technology, pp. 682-
700, Mar. 2002.
[76] Y. Theodoridis, T. Sellis, A.N. Papadopoulos, and Y. Manolopoulos,
"Specifications for Efficient Indexing in Spatiotemporal
Databases," Technical Report CH-98-01, The Chorochronos
research network project, Athens, Greece, Feb. 1998.
[77] Y. Theodoridis, J.R.O. Silva, and M.A. Nascimento, "On the
Generation of Spatiotemporal Datasets," Proc. Int'l Symp. Large
Spatial Databases, pp. 147-164, July 1999.
[78] N. Tryfona and C.S. Jensen, "Conceptual Data Modeling for
Spatiotemporal Applications," GeoInformatica, vol. 3, no. 3, pp. 245-
268, 1999.
[79] P.A. Tuma, "Implementing Historical Aggregates in TempIS,"
master's thesis, Wayne State Univ., Detroit, Mich., Nov. 1992,
[80] J.W. van Roessel, "Design of a Spatial Data Structure Using the
Relational Normal Form," Int'l J. Geographical Information Systems,
vol. 1, no. 1, pp. 33-50, 1987.
[81] M. Wang, J.S. Vitter, L. Lim, and S. Padmanabhan, "Wavelet-
Based Cost Estimation for Spatial Queries," Proc. Int'l Symp.
Advances in Spatial and Temporal Databases, pp. 175-193, July 2001.
[82] M.F. Worboys, "A Unified Model for Spatial and Temporal
Information," The Computer J., vol. 37, no. 1, pp. 26-34, 1994.
[83] W.P. Yan and P.-A. Larson, "Eager Aggregation and Lazy
Aggregation," Proc. VLDB Conf., pp. 345-357, Sept. 1995.
[84] J. Yang and J. Widom, "Incremental Computation and Maintenance
of Temporal Aggregates," Proc. Int'l Conf. Data Eng.,
pp. 51-60, Apr. 2001.
[85] X. Ye and J.A. Keane, "Processing Temporal Aggregates in
Parallel," Proc. IEEE Int'l Conf. Systems, Man, and Cybernetics,
pp. 1373-1378, Oct. 1997.
[86] C. Zaniolo, S. Ceri, C. Faloutsos, R.T. Snodgrass, V.S. Subrahmanian,
and R. Zicari, Advanced Database Systems. San Francisco:
Morgan Kaufmann, 1997.
[87] D. Zhang, "Aggregation Computation over Complex Objects,"
PhD thesis, Univ. of California, Riverside, Aug. 2002.
[88] D. Zhang, D. Gunopulos, V.J. Tsotras, and B. Seeger, "Temporal
Aggregation over Data Streams Using Multiple Granularities,"
Proc. Conf. Extending Database Technology, pp. 646-663, Mar. 2002.
[89] D. Zhang, A. Markowetz, V.J. Tsotras, D. Gunopulos, and B.
Seeger, "Efficient Computation of Temporal Aggregates with
Range Predicates," Proc. ACM SIGACT-SIGMOD-SIGART Symp.
Principles of Database Systems, pp. 237-245, May 2001.
[90] D. Zhang and V.J. Tsotras, "Improving Min/Max Aggregation
over Spatial Objects," Proc. ACM Int'l Symp. Advances in Geographic
Information Systems (ACM-GIS), pp. 88-93, Nov. 2001.
[91] D. Zhang, V.J. Tsotras, and D. Gunopulos, "Efficient Aggregation
over Objects with Extent," Proc. ACM SIGACT-SIGMOD-SIGART
Symp. Principles of Database Systems, pp. 121-132, June 2002.
--
[垃圾桶] 裡沒有會話群組。 當您有超過 6323.752806 MB (還在增加中) 的免費儲存空間時，誰還需要刪除郵件？！
沒有留言:
張貼留言