A Survey on Bitmap Index Technologies for Large-Scale Data Retrieval

Modern research equipment such as telescopes, particle colliders, and supercomputers is generating so large amounts of data. Consequently, many scientists worry that they will not be able to keep pace with the deluge. The extremely large data volumes have brought great challenge to retrieve the relatively small percentage of records which are essential for further research. The main index technologies include four categories: B-tree index, R-tree index, Hash index and bitmap index. In these technologies, the first three are traditional methods, and the last is a new one. In this paper, we focus on the survey of bitmap index, including the related techniques and applications. The relevant technologies of bitmap index are compression, binning and encoding. Two implementations of bitmap index, namely Fast Bit and RID Bit, are briefly highlighted. Meanwhile, Fast Query is mentioned, which is built on the Fast Bit bitmap indexing. We also present the latest innovative applications of bitmap index. Our survey indicates that Fast Bit indexes provide very efficient searching and retrieval operations compared with B-tree variants. However, Fast Query may perform better than Fast bit for sub-array queries or the data format has a limit. Finally, the future works are described.