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 p...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.展开更多
基金supported in part by the National Natural Science Foundation of China(Nos.61472200 and 61233016)the National Key Basic Research and Development(973)Program of China(No.2013CB228206)+1 种基金the State Grid R&D Project Architecture of Information Communication System for Energy Internet(No.SGRIXTKJ[2015]253)the National Training Program of Innovation and Entrepreneurship for Undergraduates(Nos.201510003049 and 201510003B066)
文摘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.
