Sirirut VANICHAYOBON, Naphat KEAWPIBAL, Ladda PREECHAVEERAKUL

HyBiX: A novel encoding bitmap index for space- and time-efficient query processing

A bitmap-based index is an effective and efficient indexing method for answering selective queries in a readonly environment. It offers improved query execution time by applying low-cost Boolean operators on the index directly, before accessing raw data. A drawback of the bitmap index is that index size increases with the cardinality of indexed attributes, which additionally has an impact on a query execution time. This impact is related to an increase of query execution time due to the scanning of bitmap vectors to answer the queries. In this paper, we propose a new encoding bitmap index, called the HyBiX bitmap index. The HyBiX bitmap index was experimentally compared to existing encoding bitmap indexes in terms of space requirement, query execution time, and space and time trade-off for equality and range queries. As experimental results, the HyBiX bitmap index can reduce space requirements with high cardinality attributes with satisfactory execution times for both equality and range queries. The performance of the HyBiX bitmap index provides the second-best results for equality queries and the first-best for range queries in terms of space and time trade-off.

PDF

___

[1] Sagiroglu S, Sinanc D. Big data: a review. In: 2013 International Conference on Collaboration Technologies and Systems; San Diego, CA, USA; 2013. pp. 42-47.
[2] Kambatla K, Kollias G, Kumar V, Grama A. Trends in big data analytics. Journal of Parallel and Distributed Computing 2014; 74 (7): 2561-2573. doi: 10.1016/j.jpdc.2014.01.003
[3] Thanekar SA, Subrahmanyam K, Bagwan AB. Big data and mapreduce challenges, opportunities and trends. International Journal of Electrical and Computer Engineering 2016; 6 (6): 2911-2919.
[4] Gani A, Siddiqa A, Shamshirband S, Hanum F. A survey on indexing techniques for big data: taxonomy and performance evaluation. Knowledge and Information Systems 2016; 46 (2): 241-284.
[5] Chan CY, Ioannidis YE. Bitmap index design and evaluation. ACM SIGMOD Record 1998; 27 (2): 355-366.
[6] Sohrabi MK, Azgomi H. TSGV: A table-like structure-based greedy method for materialized view selection in data warehouses. Turkish Journal of Electrical Engineering & Computer Sciences 2017; 25 (4): 3175-3187. doi: 10.3906/elk-1608-112
[7] Silberschatz A, Korth HF, Sudarshan S. Database System Concepts. New York, NY, USA: McGraw-Hill, 2011.
[8] Stallings W. Computer Organization and Architecture Designing for Performance. Upper Saddle River, NJ, USA: Prentice Hall Press, 2012.
[9] Lu J, Feng J. A survey of MapReduce based parallel processing technologies. China Communications 2014; 11 (14): 146-155. doi: 10.1109/CC.2014.7085615
[10] Stockinger K, Wu K. Bitmap indices for data warehouses. In: Wrembel R, Koncilia C (editors). Data Warehouses and OLAP Concepts Architectures and Solutions. Hershey, PA, USA: IGI Global, 2007. pp. 157-178.
[11] Chen Z, Wen Y, Cao J, Zheng W, Chang J et al. A survey of bitmap index compression algorithms for big data. Tsinghua Science and Technology 2015; 20 (1): 100-115. doi: 10.1109/TST.2015.7040519
[12] Qin X. Performance comparison of index schemes for range query of big data. In: 2016 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery; Changsha, China; 2016. pp. 1469-1473.
[13] Chaudhuri S, Dayal U. An overview of data warehousing and OLAP technology. ACM SIGMOD Record 1997; 26 (1): 65-74. doi: 10.1145/248603.248616
[14] Mei Y, Ji K, Wang F. A survey on bitmap index technologies for large-scale data retrieval. In: 2013 6th International Conference on Intelligent Networks and Intelligent Systems; Shenyang, China; 2013. pp. 316-319.
[15] O’Neil P, Quass D. Improved query performance with variant indexes. ACM SIGMOD Record 1997; 26 (2): 38-49. doi: 10.1145/253262.253268
[16] Guzun G, Canahuate G. Performance evaluation of word-aligned compression methods for bitmap indices. Knowledge and Information Systems 2016; 48: (2) 277-304. doi: 10.1007/s10115-015-0877-9
[17] Prakash KS, Prathap PMJ. Evaluating aggregate functions of iceberg query using priority based bitmap indexing strategy. International Journal of Electrical and Computer Engineering 2017; 7 (6): 3745-3752.
[18] Abdulhadi ZQ, Zuping Z, Housien HI. Bitmap index as effective indexing for low cardinality column in data warehouse. International Journal of Computer Applications 2013; 68 (24): 38-42.
[19] Wu K, Shoshani A, Stockinger K. Analyses of multi-level and multi-component compressed bitmap indexes. ACM Transactions on Database Systems 2010; 35 (1): 1-52. doi: 10.1145/1670243.1670245
[20] Antoshenkov G. Byte-aligned bitmap compression. In: DCC ’95 Data Compression Conference; Snowbird, UT, USA; 1995. p. 476.
[21] Wu K, Otoo EJ, Shoshani A. Optimizing bitmap indices with efficient compression. ACM Transactions on Database Systems 2006; 31 (1): 1-38. doi: 10.1145/1132863.1132864
[22] Stabno M, Wrembel R. RLH: Bitmap compression technique based on run-length and Huffman encoding. Information Systems 2009; 34 (4): 400-414. doi: 10.1016/j.is.2008.11.002
[23] Wen Y, Chen Z, Ma G, Cao J, Zheng W et al. SECOMPAX: A bitmap index compression algorithm. In: 2014 23rd International Conference on Computer Communications and Networks; Shanghai, China; 2014. pp. 1-7.
[24] Chang J, Chen Z, Zheng W, Cao J, Wen Y et al. SPLWAH: A bitmap index compression scheme for searching in archival Internet traffic. In: 2015 IEEE International Conference on Communications; London, UK; 2015. pp. 7089-7094.
[25] Kim S, Lee J, Satti SR, Moon B. SBH: Super byte-aligned hybrid bitmap compression. Information Systems 2016; 62: 155-168. doi: 10.1016/j.is.2016.07.004
[26] Wu Y, Chen Z, Wen Y, Zheng W, Cao J. COMBAT: A new bitmap index coding algorithm for big data. Tsinghua Science and Technology 2016; 21 (2): 136-145. doi: 10.1109/TST.2016.7442497
[27] Li C, Chen Z, Zheng W, Wu Y, Cao J. BAH: A bitmap index compression algorithm for fast data retrieval. In: 2016 IEEE 41st Conference on Local Computer Networks; Dubai, United Arab Emirates; 2016. pp. 697-705.
[28] Goyal N, Sharma Y. New binning strategy for bitmap indices on high cardinality attributes. In: 2nd Bangalore Annual COMPUTE Conference; Bangalore, India; 2009. pp. 1-5.
[29] Kim JW. Binning strategy for hierarchical bitmap indices with large scale domain hierarchy. International Journal of Applied Engineering Research 2016; 11 (18): 9289-9296.
[30] Wu KL, Yu PS. Range-based bitmap indexing for high cardinality attributes with skew. In: Twenty-Second Annual International Computer Software and Applications Conference; Vienna, Austria; 1998. pp. 61-66.
[31] Chan CY, Ioannidis YE. An efficient bitmap encoding scheme for selection queries. ACM SIGMOD Record 1999; 28 (2): 215-226. doi: 10.1145/304181.304201
[32] Wu MC, Buchmann AP. Encoded bitmap indexing for data warehouses. In: 14th International Conference on Data Engineering; Orlando, FL, USA; 1998. pp. 220-230.
[33] Wattanakitrungroj N, Vanichayobon S. Dual bitmap index: Space-time efficient bitmap index for equality and membership queries. In: 2006 International Symposium on Communications and Information Technologies; Bangkok, Thailand; 2006. pp. 568-573.
[34] Bhan M, Rajanikanth K, and Kumar STV. Multi-level and multi-component bitmap encoding for efficient search operations. Database Systems Journal 2012; 3 (4): 47-60.
[35] Alam MGR, Arafat MY, Iftekhar MKU. A new approach of dynamic Encoded bitmap indexing technique based on query history. In: 2008 International Conference on Electrical and Computer Engineering; Dhaka, Bangladesh; 2008. pp. 974-979.
[36] Sainui J, Vanichayobon S, Wattanakitrungroj N. Optimizing encoded bitmap index using frequent itemsets mining. In: 2008 International Conference on Computer and Electrical Engineering; Phuket, Thailand; 2008. pp. 511-515.
[37] Keawpibal A, Wattanakitrungroj N, Vanichayobon S. Enhanced encoded bitmap index for equality query. In: 2012 8th International Conference on Computing Technology and Information Management; Seoul, South Korea; 2012. pp. 293-298.
[38] Keawpibal N, Duangsuwan J, Wettayaprasit W, Preechaveerakul L, Vanichayobon S. DistEQ: Distributed equality query processing on Encoded bitmap index. In: 2015 12th International Joint Conference on Computer Science and Software Engineering; Songkhla, Thailand; 2015. pp. 309-314.
[39] Keawpibal N, Preechaveerakul L, Vanichayobon S. Optimizing range query processing for Dual bitmap index. Walailak Journal of Science and Technology 2019; 16 (2): 133-142.
[40] Keawpibal N. HyBiX: Hybrid encoding bitmap index for efficient space and query processing time. PhD, Prince of Songkla University, Songkhla, Thailand, 2018.