nach oben

Erschienen in:

01.01.2012

The SB-index and the HSB-index: efficient indices for spatial data warehouses

verfasst von: Thiago Luís Lopes Siqueira, Cristina Dutra de Aguiar Ciferri, Valéria Cesário Times, Ricardo Rodrigues Ciferri

Erschienen in: GeoInformatica | Ausgabe 1/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Provably correct and complete transaction rules for updating 3D city models

Nächster Artikel Integrating GI with non-GI services—showcasing interoperability in a heterogeneous service-oriented architecture

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Mateus RC, Times VC, Siqueira TL, Ciferri RR, Ciferri CDA (2010) How does the spatial data redundancy affect query performance in geographic data warehouses? Journal of Information and Data Management 1:519–534

Sampaio MC, Sousa AG, Baptista CS (2006) Towards a logical multidimensional model for spatial data warehousing and OLAP, Proceedings of the 9th ACM International Workshop on Data warehousing and OLAP, New York, NY, USA: ACM, pp. 83–90

Malinowski E, Zimányi E (2007) Logical representation of a conceptual model for spatial data warehouses. Geoinformatica 11:431–457CrossRef

Bimonte S, Tchounikine A, Miquel M (2005) Towards a spatial multidimensional model. Proceedings of the 8th ACM International Workshop on Data Warehousing and OLAP, New York, NY, USA: ACM, pp. 39–46

Rivest S, Bédard Y, Proulx M, Nadeau M, Hubert F, Pastor J (2005) SOLAP technology: merging business intelligence with geospatial technology for interactive spatio-temporal exploration and analysis of data. ISPRS J Photogramm Remote Sens 60:17–33CrossRef

Kimball R, Ross M (2002) The data warehouse toolkit: the complete guide to dimensional modeling. Wiley, New York

Harinarayan V, Rajaraman A, Ullman JD (1996) Implementing data cubes efficiently. SIGMOD Rec 25:205–216CrossRef

Malinowski E, Zimányi E (2008) Advanced data warehouse design: from conventional to spatial and temporal applications (Data-centric systems and applications). Springer

Stefanovic N, Han J, Koperski K (2000) Object-Based Selective Materialization for Efficient Implementation of Spatial Data Cubes. IEEE Trans Knowl Data Eng 12:938–958CrossRef

10.

Papadias D, Kalnis P, Zhang J, Tao Y (2001) Efficient OLAP Operations in spatial data warehouses. Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases. Springer-Verlag, London, pp 443–459

11.

Rao F, Zhang L, Yu XL, Li Y, Chen Y (2003) Spatial hierarchy and OLAP-favored search in spatial data warehouse. Proceedings of the 6th ACM International Workshop on Data Warehousing and OLAP. ACM, New York, pp 48–55

12.

Malinowski E, Zimányi E (2005) Spatial Hierarchies and Topological Relationships in the Spatial MultiDimER Model. In: Jackson M, Nelson D, Stirk S (eds) British National Conference on Databases. Springer, Sunderland, UK, pp. 17–28

13.

Ruiz CV, Times VC (2009) A Taxonomy of SOLAP Operators, Proceedings of the 24th Brazilian Symposium on Database. SBC, Porto Alegre, pp 151–165

14.

Gaede V, Günther O (1998) Multidimensional access methods. ACM Comput Surv 30:170–231CrossRef

15.

Pourabbas E, Rafanelli M (1999) Characterization of hierarchies and some operators in OLAP environment, Proceedings of the 2nd ACM International Workshop on Data Warehousing and OLAP. ACM, New York, pp 54–59

16.

Baikousi E, Vassiliadis P (2009) View usability and safety for the answering of top-k queries via materialized views, Proceeding of the ACM 12th International Workshop on Data Warehousing and OLAP. ACM, New York, pp 97–104

17.

Golfarelli M, Maniezzo V, Rizzi S (2004) Materialization of fragmented views in multidimensional databases. Data Knowl Eng 49:325–351CrossRef

18.

Ciferri CD, Ciferri RR, Forlani DT, Traina AJ, Souza FF (2007) Horizontal fragmentation as a technique to improve the performance of drill-down and roll-up queries, Proceedings of the 2007 ACM Symposium on Applied computing. ACM, New York, pp 494–499

19.

Bellatreche L, Woameno KY (2009) Dimension table driven approach to referential partition relational data warehouses, Proceeding of the ACM 12th International Workshop on Data Warehousing and OLAP. ACM, New York, pp 9–16

20.

Gorawski M, Gorawski M (2006) Balanced Spatio-Temporal Data Warehouse with R-MVB, STCAT and BITMAP Indexes”, Proceedings of the 5th International Symposium on Parallel Computing in Electrical Engineering. Washington, IEEE Computer Society, pp 43–48

21.

Wehrle P, Miquel M, Tchounikine A (2007) A grid services-oriented architecture for efficient operation of distributed data warehouses on globus, Proceedings of the 21st International Conference on Advanced Networking and Applications. IEEE Computer Society, Washington, pp 994–999

22.

Siqueira TL, Ciferri RR, Ciferri CD, Times VC (2008) Investigating the effects of spatial data redundancy in query performance over geographical data warehouses, Proceedings of the 10th Brazilian Symposium on Geoinformatics. SBC, Rio de Janeiro, pp 1–12

23.

Siqueira TL, Ciferri RR, Times VC, Ciferri CD (2009) A spatial bitmap-based index for geographical data warehouses, Proceedings of the 24th ACM Symposium on Applied Computing. ACM, New York, pp 1336–1342

24.

Siqueira TL, Ciferri CD, Times VC, Oliveira AG, Ciferri RR (2009) The impact of spatial data redundancy on SOLAP query performance. J Braz Comput Soc 15:19–34CrossRef

25.

O’Neil P, Graefe G (1995) Multi-table joins through bitmapped join indices. SIGMOD Rec 24:8–11CrossRef

26.

Jürgens M, Lenz H (1999) Tree based indexes vs. Bitmap indexes: a performance study, Proceedings of the 1st International Workshop on Design and Management of Data Warehouses. CEUR-WS.org, Heidelberg, pp. 14–15

27.

Mohan P, Wilson RE, Shekhar S, George B, Levine N, Celik M (2008) Should SDBMS support a join index?: a case study from CrimeStat, Proceedings of the 16th International Conference on Advances in Geographic Information Systems. ACM, New York, pp 1–10

28.

Papadias D, Tao Y, Kalnis P, Zhang J (2002) Indexing spatio-temporal data warehouses, Proceedings of the 18th International Conference on Data Engineering. IEEE Computer Society, Washington, pp 166–175

29.

O'Neil P, Quass D (1997) Improved query performance with variant indexes, Proceedings of the 1997 ACM SIGMOD International Conference on Management of data. New York, ACM, pp 38–49CrossRef

30.

Stockinger K, Wu K (2006) Bitmap Indices for Data Warehouses. In: Wrembel R, Koncilia C (eds) Data Warehouses and OLAP. IRM Press, pp. 157–178

31.

Chen L (2009) Curse of dimensionality. Encyclopedia of database systems. Springer, pp. 545–546

32.

Wu K, Otoo EJ, Shoshani A (2006) Optimizing bitmap indices with efficient compression. ACM Trans Database Syst 31:1–38CrossRef

33.

Wu K, Stockinger K, Shoshani A (2008) Breaking the curse of cardinality on bitmap indexes. In: Ludäscher B, Mamoulis N (eds) Scientific and statistical database management conference. Springer, Hong Kong, pp. 348–365

34.

Chan C, Ioannidis YE (1999) An efficient bitmap encoding scheme for selection queries, Proceedings of the 1999 ACM SIGMOD International Conference on Management of data. ACM, New York, pp 215–226

35.

O’Neil P, O’Neil E, Chen X, Revilak S (2009) The Star Schema Benchmark and Augmented Fact Table Indexing, Proceedings of the 1st Transaction Processing Performance Council Technology Conference. Springer LNCS 5895, Lyon, pp. 237–252

36.

Wu K, Ahern S, Bethel EW, Chen J, Childs H, Cormier-Michel E, Geddes C, Gu J, Hagen H, Hamann B, Koegler W, Lauret J, Meredith J, Messmer P, Otoo E, Perevoztchikov V, Poskanzer A, Prabhat, Rübel O, Shoshani A, Sim A, Stockinger K, Weber G, Zhang W (2009) FastBit: interactively searching massive data. J Phys Conf Ser 180:12053CrossRef

37.

O’Neil E, O’Neil P, Wu K (2007) Bitmap index design choices and their performance implications, Proceedings of the 11th International Database Engineering and Applications Symposium. IEEE Computer Society, Washington, pp 72–84

38.

Guttman A (1984) R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data. ACM, New York, pp 47–57

39.

Aoki PM (1997) Generalizing “Search” in generalized search trees, Proceedings of the 14th International Conference on Data Engineering. IEE Computer Society, Washington, pp 380–389

40.

Beckmann N, Kriegel H, Schneider R, Seeger B (1990) The R*-tree: an efficient and robust access method for points and rectangles. SIGMOD Rec 19:322–331CrossRef

41.

Bellatreche L, Boukhalfa K (2010) Yet Another Algorithms for Selecting Bitmap Join Indexes, Proceedings of the 12th International Conference on Data Warehousing and Knowledge Discovery, Springer LNCS 6263, Bilbao, pp 105–116

42.

Morales T, Rich K (2009) Oracle database reference, 11 g Release 1, Oracle Corporation. Available at http://www.oracle.com/pls/db111/homepage

43.

Chmiel J, Morzy T, Wrembel R (2009) HOBI: Hierarchically Organized Bitmap Index for Indexing Dimensional Data, Proceedings of the 11th International Conference on Data Warehousing and Knowledge Discovery, Springer LNCS 5691, pp. 87–98

44.

Morzy M, Morzy T, Nanopoulos A, Manolopoulos Y (2003) Hierarchical Bitmap Index: an efficient and scalable indexing technique for set-valued attributes, Proceedings of the 7th East European Conference on Advances in Databases and Information Systems, Springer LNCS 2798, pp. 236–252

Titel: The SB-index and the HSB-index: efficient indices for spatial data warehouses
verfasst von: Thiago Luís Lopes Siqueira
Cristina Dutra de Aguiar Ciferri
Valéria Cesário Times
Ricardo Rodrigues Ciferri
Publikationsdatum: 01.01.2012
Verlag: Springer US
Erschienen in: GeoInformatica / Ausgabe 1/2012
Print ISSN: 1384-6175
Elektronische ISSN: 1573-7624
DOI: https://doi.org/10.1007/s10707-011-0128-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2012

Reference model for a data grid approach to address data in a dynamic SDI

Provably correct and complete transaction rules for updating 3D city models

Automatic geospatial metadata generation for earth science virtual data products

Topological operators: a relaxed query processing approach

An evaluation of ontology matching in geo-service applications

Integrating GI with non-GI services—showcasing interoperability in a heterogeneous service-oriented architecture