Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Data aggregation in Geographic Information Systems (GIS) is a desirable feature, although only marginally present in commercial systems, which also fail to provide integration between GIS and OLAP (On Line Analytical Processing). With this in mind, we have developed Piet, a system that makes use of a novel query processing technique: first, a process called sub-polygonization decomposes each thematic layer in a GIS, into open convex polygons; then, another process computes and stores in a database the overlay of those layers for later use by a query processor. We describe the implementation of Piet, and provide experimental evidence that overlay precomputation can outperform GIS systems that employ indexing schemes based on R-trees.

REFERENCES

• 1: 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
• 2: S. Haesevoets, B. Kuijpers, and A. Vaisman. Spatial aggregation: Data model and implementation. In Submitted for revew, 2007.
• 3: Jiawei Han , Nebojsa Stefanovic , Krzysztof Koperski, Selective Materialization: An Efficient Method for Spatial Data Cube Construction, Proceedings of the Second Pacific-Asia Conference on Research and Development in Knowledge Discovery and Data Mining, p.144-158, April 15-17, 1998
• 4: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 5: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 6: Maintaining Data Cubes under Dimension Updates, Proceedings of the 15th International Conference on Data Engineering, p.346, March 23-26, 1999
• 7: Christian S. Jensen , Augustas Kligys , Torben Bach Pedersen , Igor Timko, Multidimensional data modeling for location-based services, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.1, p.1-21, January 2004 [doi>10.1007/s00778-003-0091-3]
• 8: Ralph Kimball , Margy Ross, The Data Warehouse Toolkit: The Complete Guide to Dimensional Modeling, John Wiley & Sons, Inc., New York, NY, 2002
• 9: B. Kuijpers and Alejandro Vaisman. A data model for moving objects supporting aggregation. In Proceedings of STDM'07, Istambul, Turkey, 2007.
• 10: G. Kuper and M. Scholl. Geographic information systems. In J. Paredaens, G. Kuper, and L. Libkin, editors, Constraint databases, chapter 12, pages 175--198. Springer-Verlag, 2000.
• 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: J. Paredaens, G. Kuper, and L. Libkin, editors. Constraint databases. Springer-Verlag, 2000.
• 13: Torben Bach Pedersen , Nectaria Tryfona, Pre-aggregation in Spatial Data Warehouses, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.460-480, July 12-15, 2001
• 14: Fangyan Rao , Long Zhang , Xiu Lan Yu , Ying Li , Ying Chen, Spatial hierarchy and OLAP-favored search in spatial data warehouse, Proceedings of the 6th ACM international workshop on Data warehousing and OLAP, November 07-07, 2003, New Orleans, Louisiana, USA [doi>10.1145/956060.956070]
• 15: P. Rigaux, M. Scholl, and A. Voisard. Spatial Databases. Morgan Kaufmann, 2002.
• 16: S. Rivest, Y. Bédard, and P. Marchand. Modeling multidimensional spatio-temporal data warehouses in a context of evolving specifications. Geomatica, 55 (4), 2001.
• 17: G. Shilov, B. Gurevich. Integral, Measure, and Derivative: A Unified Approach. Richard A. Silverman, trans. Dover Publications, 1978.
• 18: Ines Fernando Vega Lopez , Richard T. Snodgrass , Bongki Moon, Spatiotemporal Aggregate Computation: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.17 n.2, p.271-286, February 2005 [doi>10.1109/TKDE.2005.34]
• 19: Michael Worboys , Matt Duckham, GIS: A Computing Perspective, 2nd Edition, CRC Press, Inc., Boca Raton, FL, 2004

INDEX TERMS

General Terms:
Experimentation, Performance

Keywords:
GIS, OLAP, view materialization