Spatial hierarchy and OLAP-favored search in spatial data warehouse

ABSTRACT

Data warehouse and Online Analytical Processing(OLAP) play a key role in business intelligent systems. With the increasing amount of spatial data stored in business database, how to utilize these spatial information to get insight into business data from the geo-spatial point of view is becoming an important issue of data warehouse and OLAP. However, traditional data warehouse and OLAP tools can not fully exploit spatial data in coordinates because multi-dimensional spatial data does not have implicit or explicit concept hierarchy to compute pre-aggregation and materialization in data warehouse. In this paper we extend the traditional set-grouping hierarchy into multi-dimensional data space and propose to use spatial index tree as the hierarchy on spatial dimension. With spatial hierarchy, spatial data warehouse can be built accordingly. Our approach preserve the star schema in data warehouse while building the hierarchy on spatial dimension, and can be easily integrated into existing data warehouse and OLAP systems. To process spatial OLAP query in spatial data warehouse, we propose an OLAP-favored search method which can utilize the pre-aggregation result in spatial data warehouse to improve the performance of spatial OLAP queries. For generality, the algorithm is developed based on Generalized Index Searching Tree(GiST). To improve the performance of OLAP-favored search, we further introduce a heuristic search method which can provide an approximate answer to spatial OLAP query. Experiment result shows the efficiency of our method.

REFERENCES

• 1: David W. Adler, DB2 Spatial Extender - Spatial data within the RDBMS, Proceedings of the 27th International Conference on Very Large Data Bases, p.687-690, September 11-14, 2001
• 2: Paul M. Aoki, Generalizing "Search'' in Generalized Search Trees (Extended Abstract), Proceedings of the Fourteenth International Conference on Data Engineering, p.380-389, February 23-27, 1998
• 3: 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
• 4: M. C. Chen , L. P. McNamee, On the Data Model and Access Method of Summary Data Management, IEEE Transactions on Knowledge and Data Engineering, v.1 n.4, p.519-529, December 1989 [doi>10.1109/69.43426]
• 5: N. Colossi , W. Malloy , B. Reinwald, Relational extensions for OLAP, IBM Systems Journal, v.41 n.4, p.714-731, October 2002
• 6: I. Daratech. Daratech: Geographic information systems markets and opportunities. 2000.
• 7: R. A. Finkel and J. L. Bentley. Quad trees: A data structure for retrieval on composite keys. Acta Informatica, 4:1--9, 1974.
• 8: 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]
• 9: Sakti P. Ghosh, SIAM: statistics information access method, Proceedings of the 3rd international workshop on Statistical and scientific database management, p.286-293, July 22-24, 1986
• 10: 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]
• 11: 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
• 12: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 13: 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
• 14: Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer, Generalized Search Trees for Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.562-573, September 11-15, 1995
• 15: W. H. Inmon, Building the data warehouse, QED Information Sciences, Inc., Wellesley, MA, 1992
• 16: Y. Li, Y. Chen, and F. Y. Rao. The approach for data warehouse to answering spatial OLAP queries. In the Fourth International Intelligent Data Engineering and Automated Learning, 2003.
• 17: D. Papadias, P. Kalnis, J. Zhang, and Y. Tao. Efficient OLAP operations in spatial data warehouses. Lecture Notes in Computer Science, 2001.
• 18: D. Papadias, Y. Tao, P. Kalnis, and J. Zhang. Indexing spatio-temporal data warehouses. In ICDE, 2002.
• 19: Ravi Kanth V Kothuri , Siva Ravada , Daniel Abugov, Quadtree and R-tree indexes in oracle spatial: a comparison using GIS data, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564755]
• 20: 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]
• 21: 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
• 22: Jaideep Srivastava , Vincent Y. Lum, A Tree Based Access Method (TBSAM) for Fast Processing of Aggregate Queries, Proceedings of the Fourth International Conference on Data Engineering, p.504-510, February 01-05, 1988
• 23: TIGER/Line files technical documentation, US Census Bureau, 2002.
• 24: L. Zhang, Y. Li, F. Rao, X. Yu, and Y. Chen. An approach to enabling spatial OLAP by aggregating on spatial hierarchy. In Proc. Data Warehousing and Knowledge Discovery DaWaK, 2003.

INDEX TERMS

General Terms:
Algorithms, Performance

Keywords:
spatial OLAP, spatial data warehouse, spatial hierarchy