HyBiX: Hybrid encoding bitmap index for efficient space and query processing time

Abstract

With an increasing availability of technology, an enormous amount of data has been generated. The problems in the storage and access have emerged. The consequent need for efficient techniques to store and access the information has been a strong resurgence of interest in the area of information retrieval. A bitmap-based index is an effective and efficient indexing method for operating information retrieval in a read-only environment. It offers improved query execution time by applying low-cost Boolean operators on the index directly, before accessing raw data. However, a drawback of the bitmap index is that the index size increases with the cardinality of indexed attributes. This dissertation then proposes a new encoding bitmap index, called HyBiX bitmap index. The basic concept of HyBiX bitmap index is the use of grouping idea with attribute values and the encoding design of existing encoding bitmap indexes in order to improve both storage demanded and execution time consumed with various queries. Particularly, the grouping of attribute values facilitates in answering a continuous range of query values. The experiment show that the HyBiX bitmap index takes 79% and 82% faster execution times than the Encoded bitmap index, for equality and range queries, respectively. Furthermore, the performance of HyBiX bitmap index in terms of space and time trade-off achieves the third-best and first-best as compare to existing encoding bitmap index, for equality and range queries, respectively.