Hierarchical Bitmap Indexing for Range Queries on Multidimensional Arrays

Luboš Krčál, Shen Shyang Ho, Jan Holub

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Bitmap indices are widely used in commercial databases for processing complex queries, due to their efficient use of bit-wise operations. Bitmap indices apply natively to relational and linear datasets, with distinct separation of the columns or attributes, but do not perform well on multidimensional array scientific data. We propose a new method for multidimensional array indexing that considers the spatial component of multidimensional arrays. The hierarchical indexing method is based on sparse n-dimensional trees for dimension partitioning, and bitmap indexing with adaptive binning for attribute partitioning. This indexing performs well on range queries involving both dimension and attribute constraints, as it prunes the search space early. Moreover, the indexing is easily extensible to membership queries. The indexing method was implemented on top of a state of the art bitmap indexing library Fastbit, using tables partitioned along any subset of the data dimensions. We show that the hierarchical bitmap index outperforms conventional bitmap indexing, where an auxiliary attribute is required for each dimension. Furthermore, the adaptive binning significantly reduces the amount of bins and therefore memory requirements.

Original languageEnglish (US)
Title of host publicationDatabase Systems for Advanced Applications - 27th International Conference, DASFAA 2022, Proceedings
EditorsArnab Bhattacharya, Janice Lee Mong Li, Divyakant Agrawal, P. Krishna Reddy, Mukesh Mohania, Anirban Mondal, Vikram Goyal, Rage Uday Kiran
PublisherSpringer Science and Business Media Deutschland GmbH
Pages509-525
Number of pages17
ISBN (Print)9783031001222
DOIs
StatePublished - 2022
Event27th International Conference on Database Systems for Advanced Applications, DASFAA 2022 - Virtual, Online
Duration: Apr 11 2022Apr 14 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13245 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference27th International Conference on Database Systems for Advanced Applications, DASFAA 2022
CityVirtual, Online
Period4/11/224/14/22

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Hierarchical Bitmap Indexing for Range Queries on Multidimensional Arrays'. Together they form a unique fingerprint.

Cite this