Efficient aggregation over objects with extent

ABSTRACT

We examine the problem of efficiently computing sum/count/avg aggregates over objects with non-zero extent. Recent work on computing multi-dimensional aggregates has concentrated on objects with zero extent (points) on a multi-dimensional grid, or one-dimensional intervals. However, in many spatial and/or spatio-temporal applications objects have extent in various dimensions, while they can be located anywhere in the application space. The aggregation predicate is typically described by a multi-dimensional box (box-sum aggregation). We examine two variations of the problem. In the simple case an object's value contributes to the aggregation result as a whole as long as the object intersects the query box. More complex is the functional box-sum aggregation introduced in this paper, where objects participate in the aggregation proportionally to the size of their intersection with the query box. We first show that both problems can he reduced to dominance-sum queries. Traditionally dominance-sum queries are addressed in main memory by a static structure, the ECDF-tree. We then propose two extensions, namely the ECDF-B-trees, that make this structure disk-based and dynamic. Finally, we introduce the DA-tree that combines the advantages from each ECDF-B-tree. We run experiments comparing the performance of the ECDF-B-trees, the BA-tree and a traditional R*-tree (which has been augmented to include aggregation information on its index nodes) over spatial datasets. Our evaluation reaffirms that the BA-tree has more robust performance. Compared against the augmented R*-tree, the BA-tree offers drastic improvement in query performance at the expense of some limited extra space.

REFERENCES

• 1: Sameet Agarwal , Rakesh Agrawal , Prasad Deshpande , Ashish Gupta , Jeffrey F. Naughton , Raghu Ramakrishnan , Sunita Sarawagi, On the Computation of Multidimensional Aggregates, Proceedings of the 22th International Conference on Very Large Data Bases, p.506-521, September 03-06, 1996
• 2: P. Agarwal and J. Erickson, "Geometric Range Searching and Its Relatives", Advances in Discrete and Computational Geometry, (B. Chazelle, E. Goodman and R. Pollack eds.), American Mathematical Society, Providence, 1998.
• 3: Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala, Congressional samples for approximate answering of group-by queries, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.487-498, May 15-18, 2000, Dallas, Texas, United States
• 4: Swarup Acharya , Viswanath Poosala , Sridhar Ramaswamy, Selectivity estimation in spatial databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.13-24, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 5: Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
• 6: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 7: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 8: J. L. Bentley and N. B. Saxe, "Decomposable Searching Problems I: Static-to-Dynamic Transformations", J. of Alg. 1(4), 1980.
• 9: 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]
• 10: Seok-Ju Chun , Chin-Wan Chung , Ju-Hong Lee , Seok-Lyong Lee, Dynamic Update Cube for Range-sum Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.521-530, September 11-14, 2001
• 11: Chee Yong Chan , Yannis E. Ioannidis, Hierarchical Prefix Cubes for Range-Sum Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.675-686, September 07-10, 1999
• 12: Y. Chiang and R. Tamassia, "Dynamic Algorithms in Computational Geometry", Proc. of the IEEE, Special Issue on Computational Geometry, G. Toussaint (Ed.), 80(9), 1992.
• 13: H. Edelsbrunner and M. H. Overmars, "On the Equivalence of Some Rectangle Problems", Information Processing Letters 14(3), 1982.
• 14: Steven Geffner , Divyakant Agrawal , Amr El Abbadi, The Dynamic Data Cube, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.237-253, March 27-31, 2000
• 15: S. Geffner, D. Agrawal, A. El Abbadi and T. Smith, "Relative Prefix Sums: An Efficient Approach for Querying Dynamic OLAP Data Cubes", Proc. of ICDE, 1999.
• 16: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 17: Bruce C. Huang, Parallel Algorithms for Computing Temporal Aggregates, Proceedings of the 15th International Conference on Data Engineering, p.418, March 23-26, 1999
• 18: Ching-Tien Ho , Rakesh Agrawal , Nimrod Megiddo , Ramakrishnan Srikant, Range queries in OLAP data cubes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.73-88, May 11-15, 1997, Tucson, Arizona, United States
• 19: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 20: Nick Kline , Richard Thomas Snodgrass, Computing Temporal Aggregates, Proceedings of the Eleventh International Conference on Data Engineering, p.222-231, March 06-10, 1995
• 21: Iosif Lazaridis , Sharad Mehrotra, Progressive approximate aggregate queries with a multi-resolution tree structure, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.401-412, May 21-24, 2001, Santa Barbara, California, United States
• 22: Jiří Matoušek, Geometric range searching, ACM Computing Surveys (CSUR), v.26 n.4, p.422-461, Dec. 1994 [doi>10.1145/197405.197408]
• 23: 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
• 24: Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 25: 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
• 26: Mirek Riedewald , Divyakant Agrawal , Amr El Abbadi, pCube: Update-Efficient Online Aggregation with Progressive Feedback and Error Bounds, Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00), p.95, July 26-28, 2000 [doi>10.1109/SSDM.2000.869781]
• 27: Nick Roussopoulos , Yannis Kotidis , Mema Roussopoulos, Cubetree: organization of and bulk incremental updates on the data cube, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.89-99, May 11-15, 1997, Tucson, Arizona, United States
• 28: J. Robinson, "The K-D-B Tree", Proc. of SIGMOD, 1981.
• 29: C. Sun, D. Agrawal and A. El Abbadi, "Exploring Spatial Datasets with Histograms", Proc. of ICDE, 2002.
• 30: Chengyu Sun , Divyakant Agrawal , Amr El Abbadi, Selectivity Estimation for Spatial Joins with Geometric Selections, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.609-626, March 25-27, 2002
• 31: Jayavel Shanmugasundaram , Usama Fayyad , P. S. Bradley, Compressed data cubes for OLAP aggregate query approximation on continuous dimensions, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.223-232, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312231]
• 32: Rolfe R. Schmidt , Cyrus Shahabi, How to evaluate multiple range-sum queries progressively, 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.543630]
• 33: 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
• 34: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 35: Jeffrey Scott Vitter , Min Wang, Approximate computation of multidimensional aggregates of sparse data using wavelets, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.193-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 36: Jeffrey Scott Vitter , Min Wang , Bala Iyer, Data cube approximation and histograms via wavelets, Proceedings of the seventh international conference on Information and knowledge management, p.96-104, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288645]
• 37: 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
• 38: Yihong Zhao , Prasad M. Deshpande , Jeffrey F. Naughton, An array-based algorithm for simultaneous multidimensional aggregates, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.159-170, May 11-15, 1997, Tucson, Arizona, United States
• 39: 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]
• 40: 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

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computability theory

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Mathematics and statistics

General Terms:
Design, Languages, Theory

Keywords:
aggregation, extents, functional, indexing, spatial