COMBAT: A New Bitmap Index Coding Algorithm for Big Data

Yinjun Wu

doi:10.1109/TST.2016.7442497

COMBAT: A New Bitmap Index Coding Algorithm for Big Data

2016-04-01

6

OA

AI

DOI：10.1109/TST.2016.7442497

原文链接

原文求助

摘要

En 中文

Bitmap indexing has been widely used in various applications due to its speed in bitwise operations. However, it can consume large amounts of memory. To solve this problem, various bitmap coding algorithms have been proposed. In this paper, we present COMbining Binary And Ternary encoding (COMBAT), a new bitmap index coding algorithm. Typical algorithms derived from Word Aligned Hybrid (WAH) are COMPressed Adaptive indeX (COMPAX) and Compressed n Composable Integer Set (CONCISE), which can combine either two or three continuous words after WAH encoding. COMBAT combines both mechanisms and results in more compact bitmap indexes. Moreover, querying time of COMBAT can be faster than that of COMPAX and CONCISE, since bitmap indexes are smaller and it would take less time to load them into memory. To prove the advantages of COMBAT, we extend a theoretical analysis model proposed by our group, which is composed of the analysis of various possible bitmap indexes. Some experimental results based on real data are also provided, which show COMBAT's storage and speed superiority. Our results demonstrate the advantages of COMBAT and codeword statistics are provided to solidify the proof.

Keyword:

bitmap index

big data

COMBAT

CONCISE

COMPAX

index encoding

performance evaluation

COMBAT: A New Bitmap Index Coding Algorithm for Big Data

摘要

期刊

机构

引用论文