The SB-index and the HSB-index: efficient indices for spatial data warehouses |
| |
Authors: | Thiago Luís Lopes Siqueira Cristina Dutra de Aguiar Ciferri Valéria Cesário Times Ricardo Rodrigues Ciferri |
| |
Affiliation: | (1) S?o Carlos Campus, S?o Paulo Federal Institute of Education, Science and Technology (IFSP), Rodovia Washington Luis, Km 235, 13.565-905 S?o Carlos, SP, Brazil;(2) Computer Science Department, Federal University of S?o Carlos (UFSCar), Rodovia Washington Luis, Km 235, P.O. Box 676, 13.565-905 S?o Carlos, SP, Brazil;(3) Computer Science Department, University of S?o Paulo at S?o Carlos (USP), Av. do Trabalhador S?o-Carlense, 400, P.O. Box 668, 13.560-970 S?o Carlos, SP, Brazil;(4) Informatics Center, Federal University of Pernambuco (UFPE), Av. Jornalista Anibal Fernandes, 50.740-560 Recife, PE, Brazil |
| |
Abstract: | Spatial data warehouses (SDWs) allow for spatial analysis together with analytical multidimensional queries over huge volumes
of data. The challenge is to retrieve data related to ad hoc spatial query windows according to spatial predicates, avoiding the high cost of joining large tables. Therefore, mechanisms
to provide efficient query processing over SDWs are essential. In this paper, we propose two efficient indices for SDW: the
SB-index and the HSB-index. The proposed indices share the following characteristics. They enable multidimensional queries
with spatial predicate for SDW and also support predefined spatial hierarchies. Furthermore, they compute the spatial predicate
and transform it into a conventional one, which can be evaluated together with other conventional predicates by accessing
a star-join Bitmap index. While the SB-index has a sequential data structure, the HSB-index uses a hierarchical data structure
to enable spatial objects clustering and a specialized buffer-pool to decrease the number of disk accesses. The advantages
of the SB-index and the HSB-index over the DBMS resources for SDW indexing (i.e. star-join computation and materialized views)
were investigated through performance tests, which issued roll-up operations extended with containment and intersection range
queries. The performance results showed that improvements ranged from 68% up to 99% over both the star-join computation and
the materialized view. Furthermore, the proposed indices proved to be very compact, adding only less than 1% to the storage
requirements. Therefore, both the SB-index and the HSB-index are excellent choices for SDW indexing. Choosing between the
SB-index and the HSB-index mainly depends on the query selectivity of spatial predicates. While low query selectivity benefits
the HSB-index, the SB-index provides better performance for higher query selectivity. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|