SB-Index : um índice espacial baseado em bitmap para data warehouse geográfico - Siqueira, Thiago Luís Lopes (Universidade Federal de São Carlos, 2009)
Geographic Data Warehouses (GDW) became one of the main technologies used in decision-making processes and spatial analysis since they provide the integration of Data Warehouses, On-Line Analytical Processing and Geographic Information Systems. As a result, a GDW enables spatial analyses together with agile and flexible multidimensional analytical queries over huge volumes of data. On the other hand, there is a challenge in a GDW concerning the query performance, which consists of retrieving data related to ad-hoc spatial query windows and avoiding the high cost of star-joins. Clearly, mechanisms to provide efficient query processing, as index structures, are essential. In this master s thesis, a novel index for GDW is introduced, namely the SB-index, which is based on the Bitmap Join Index and the Minimum Bounding Rectangle. The SB-index inherits the Bitmap Index legacy techniques and introduces them in GDW, as well as it enables support for predefined spatial attribute hierarchies. The SB-index validation was performed through experimental performance tests. Comparisons among the SB-index approach, the star-join aided by R-tree and the star-join aided by GiST indicated that the SB-index significantly improves the elapsed time in query processing from 76% up to 96% with regard to queries defined over the spatial predicates of intersection, enclosure and containment and applied to roll-up and drill-down operations. In addition, the impact of the increase in data volume on the performance was analyzed. The increase did not impair the performance of the SB-index, which highly improved the elapsed time in query processing. Moreover, in this master s thesis there is an experimental investigation on how does the spatial data redundancy affect query response time and storage requirements in a GDW? . Redundant and non-redundant GDW schemas were compared, concluding that redundancy is related to high performance losses. Then, aiming at improving query performance, the SB-index performance was evaluated on the redundant GDW schema. The results pointed out that SB-index significantly improves the elapsed time in query processing from 25% up to 99%. Finally, a specific enhancement of the SB-index was developed in order to deal with spatial data redundancy. With this enhancement, the minimum performance gain observed became 80%.
Keywords: Banco de dados; Data warehouse geográfico; Indexação; Índice bitmap; Geographic data warehouse; Bitmap index; Indexing; CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO