Hierarchical Bitmap Indexing for Range Queries on Multidimensional Arrays

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F22%3A00358121" target="_blank" >RIV/68407700:21240/22:00358121 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1007/978-3-031-00123-9_40" target="_blank" >http://dx.doi.org/10.1007/978-3-031-00123-9_40</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-00123-9_40" target="_blank" >10.1007/978-3-031-00123-9_40</a>

Result language

angličtina

Original language name

Hierarchical Bitmap Indexing for Range Queries on Multidimensional Arrays

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Database Systems for Advanced Applications

ISBN

978-3-031-00122-2

ISSN

0302-9743

e-ISSN

—

Number of pages

17

Pages from-to

509-525

Publisher name

Springer, Cham

Place of publication

—

Event location

Hyderabad

Event date

Apr 11, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000873153800040