A spatial bitmap-based index for geographical data warehouses

ABSTRACT

In this paper we propose the Spatial Bitmap Index (SB-index), which is an index based on Bitmap and Minimum Bounding Rectangle (MBR) to provide efficient query processing in Geographical Data Warehouses. The SB-index is built on the primary key of a spatial dimension table, and maintains the MBR of a given spatial attribute. Query processing requires a scan on the index, which compares both the query spatial predicate and the current MBR. This scan supplies a set of candidate solutions to a refinement step that evaluates each candidate. Finally, only the index entries from objects that satisfy the spatial predicate must be accessed, in order to answer the submitted query. Comparisons between the SB-index and the star-join indexed with R-tree and GiST showed significantly improvement of 25% up to 95% with regards to the query processing time. This performance gain occurs since SB-index restricts a set of candidates and avoids the star-join calculation.

REFERENCES

• 1: 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
• 2: Bimonte, S., Tchounikine, A. and Miquel, M. Spatial OLAP: Open Issues and a Web Based Prototype. In: 10th AGILE International Conference on Geographic Information Science, 2007. 11p.
• 3: S. Bimonte , A. Tchounikine , M. Miquel, Towards a spatial multidimensional model, Proceedings of the 8th ACM international workshop on Data warehousing and OLAP, November 04-05, 2005, Bremen, Germany [doi>10.1145/1097002.1097009]
• 4: Fidalgo, R. N. et al. GeoDWFrame: A Framework for Guiding the Design of Geographical Dimensional Schemas. In: 6^th DaWak, 2004. p. 26--37.
• 5: 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]
• 6: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, ACM SIGMOD Record, v.14 n.2, June 1984
• 7: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, ACM SIGMOD Record, v.25 n.2, p.205-216, June 1996
• 8: Kimball, R. and Ross, M. The Data Warehouse Toolkit. 2^nd Ed. Wiley, 2002.
• 9: Elzbieta Malinowski , Esteban Zimányi, Representing spatiality in a conceptual multidimensional model, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA [doi>10.1145/1032222.1032226]
• 10: Elizabeth O'Neil , Patrick O'Neil , Kesheng Wu, Bitmap Index Design Choices and Their Performance Implications, Proceedings of the 11th International Database Engineering and Applications Symposium, p.72-84, September 06-08, 2007 [doi>10.1109/IDEAS.2007.19]
• 11: Patrick E. O'Neil, Model 204 Architecture and Performance, Proceedings of the 2nd International Workshop on High Performance Transaction Systems, p.40-59, September 28-30, 1987
• 12: Patrick O'Neil , Goetz Graefe, Multi-table joins through bitmapped join indices, ACM SIGMOD Record, v.24 n.3, p.8-11, Sept. 1995 [doi>10.1145/211990.212001]
• 13: O'Neil, P., O'Neil, E. and Chen, X. The Star Schema Benchmark. 2007. http://www.cs.umb.edu/~poneil/starschemab.pdf
• 14: Patrick O'Neil , Dallan Quass, Improved query performance with variant indexes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.38-49, May 11-15, 1997, Tucson, Arizona, United States
• 15: 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
• 16: Nebojsa Stefanovic , Jiawei Han , Krzysztof Koperski, Object-Based Selective Materialization for Efficient Implementation of Spatial Data Cubes, IEEE Transactions on Knowledge and Data Engineering, v.12 n.6, p.938-958, November 2000 [doi>10.1109/69.895803]
• 17: Joel da Silva , Valéria C. Times , Ana Carolina Salgado, An open source and web based framework for geographic and multidimensional processing, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France [doi>10.1145/1141277.1141292]
• 18: Stockinger, K. and Wu, K. Bitmap Indices for Data Warehouses. Data Warehouses and OLAP: Concepts, Architectures and Solutions. IRM Press, 2007. p. 157--178.
• 19: Kesheng Wu , Ekow J. Otoo , Arie Shoshani, Optimizing bitmap indices with efficient compression, ACM Transactions on Database Systems (TODS), v.31 n.1, p.1-38, March 2006 [doi>10.1145/1132863.1132864]
• 20: Wu, K., Stockinger, K. and Shosani, A. Breaking the Curse of Cardinality on Bitmap Indexes. Report LBNL-173E. 2008. http://crd.lbl.gov/~kewu/ps/LBNL-173E.pdf.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Algorithms, Experimentation, Performance

Keywords:
bitmap index, geographical data warehouse, projection index