Improving min/max aggregation over spatial objects

ABSTRACT

We examine the problem of computing MIN/MAX aggregates over a collection of spatial objects. Each spatial object is associated with a weight (value), for example, the average temperature or rainfall over the area covered by the object. Given a query rectangle, the MIN/MAX problem computes the minimum/maximum weight among all objects intersecting the query rectangle. Traditionally such queries have been performed as range search queries. Assuming that the objects are indexed by a spatial access method, the MIN/MAX is computed as objects are retrieved. This requires effort proportional to the number of objects intersecting the query interval, which may be large. A better approach is to maintain aggregate information among the index nodes of the spatial access method; then various index paths can be eliminated during the range search. In this paper we propose four optimizations that further improve the performance of MIN/MAX queries. Our experiments show that the proposed optimizations offer drastic performance improvement over previous approaches. Moreover, as a by-product of this work we present an optimized version of the MSB-tree, an index that has been proposed for the MIN/MAX computation over 1-dimensional interval objects.

REFERENCES

• 1: Paul M. Aoki, How to Avoid Building DataBlades(r) That Know the Value of Everything and the Cost of Nothing, Proceedings of the 11th International Conference on Scientific on Scientific and Statistical Database Management, p.122, July 28-30, 1999 [doi>10.1109/SSDM.1999.787627]
• 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: Walid G. Aref , Hanan Samet, Efficient processing of window queries in the pyramid data structure, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.265-272, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298579]
• 4: 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]
• 5: 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
• 6: 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
• 7: 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
• 8: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 9: 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
• 10: Relative Prefix Sums: An Efficient Approach for Querying Dynamic OLAP Data Cubes, Proceedings of the 15th International Conference on Data Engineering, p.328, March 23-26, 1999
• 11: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• 12: 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
• 13: C. T. Ho, R. Agrawal, N. Megiddo and J. J. Tsay, "Techniques for Speeding up Range-Max Queries in OLAP Data Cubes", IBM Research Report, 1997. URL=http:// www.almaden.ibm.com/cs/quest/PUBS.html
• 14: M. Jürgens , H.-J. Lenz, The R-tree: An Improved R*-tree with Materialized Data for Supporting Range Queries on OLAP-Data, Proceedings of the 9th International Workshop on Database and Expert Systems Applications, p.186, August 26-28, 1998
• 15: Marcus Jürgens , Hans-J. Lenz, PISA: Performance Models for Index Structures with and without Aggregated Data, Proceedings of the 11th International Conference on Scientific on Scientific and Statistical Database Management, p.78, July 28-30, 1999 [doi>10.1109/SSDM.1999.787623]
• 16: 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
• 17: Jiří Matoušek, Geometric range searching, ACM Computing Surveys (CSUR), v.26 n.4, p.422-461, Dec. 1994 [doi>10.1145/197405.197408]
• 18: K. Mehlhorn, "Multi-dimensional Searching and Computational geometry", Data Structures and Algorithms, vol. 3, Springer-Verlag, Heidelberg, West Germany, 1984.
• 19: 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
• 20: D. Papadias, P. Kalnis, J. Zhang and Y. Tao, "Indexing Spatio-Temporal Data Warehouses", TechReport HKUST-CS01-20, CS Dept., Univ. of Sci. and Tech., Hong Kong, 2001. URL=http://www.cs.ust.hk/~dimitris/publications.html
• 21: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 22: 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
• 23: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 24: J. Yang and J. Widom, "Incremental Computation and Maintenance of Temporal Aggregates" (full version), TechReport, Stanford University, 2000. URL=http://www.cs.duke.edu/~junyang/research.html #pubs
• 25: 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
• 26: 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]
• 27: D. Zhang and V. J. Tsotras, "Improving Min/Max Aggregation over Spatial Objects", TechReport UCR\_CS\_01\_03, CS Dept., UC Riverside, 2001. URL=http://www.cs.ucr.edu/~donghui/publications/boxmax_full.ps
• 28: D. Zhang, V. J. Tsotras, D. Gunopulos and A. Markowetz, "Efficient Aggregation over Objects with Extent", TechReport UCR\_CS\_01\_01, CS Dept., UC Riverside, 2001. URL=http://www.cs.ucr.edu/~donghui/publications/boxaggr.ps

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Theory

Keywords:
Min/Max, indexing, spatial aggregates