Optimizing Range Query Processing for Dual Bitmap Index

Authors

  • Naphat KEAWPIBAL Department of Computer Science, Faculty of Science, Prince of Songkla University, Songkhla 90110
  • Ladda PREECHAVEERAKUL Department of Computer Science, Faculty of Science, Prince of Songkla University, Songkhla 90110
  • Sirirut VANICHAYOBON Department of Computer Science, Faculty of Science, Prince of Songkla University, Songkhla 90110

DOI:

https://doi.org/10.48048/wjst.2019.4146

Keywords:

Encoding bitmap indexes, dual bitmap index, range query processing, Dual-simRQ

Abstract

Bitmap-based indexes are known to be the most effective indexing method for retrieving and answering selective queries in a read-only environment. Various types of encoding bitmap indexes significantly improve query time efficiency by utilizing fast Boolean operations directly on the index before retrieving the raw data. In particular, the dual bitmap index improves the performance of equality queries in terms of the space vs. time trade-off. However, the performance of range queries is unsatisfactory. In this paper, an optimizing algorithm is proposed to improve the range query processing for the dual bitmap index. The results of the experiment conducted show that the proposed algorithm, called Dual-simRQ, reduces the number of bitmap vectors scanned and the Boolean operations performed, which impacts the overall performance for range query processing.

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...

References

S Sagiroglu and D Sinanc. Big data: A review. In: Proceedings of 2013 International Conference on Collaboration Technologies and Systems, San Diego, USA, 2013, p. 42-7.

S Chaudhuri. What next? A half-dozen data management research goals for big data and the cloud. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Scottsdale, Arizona, USA, 2012, p. 1-4.

A Katal, M Wazid and R H Goudar. Big data: Issues, challenges, tools and good practices. In: Proceedings of 2013 6th International Conference on Contemporary Computing, Noida, India, 2013, p. 404-9.

S Chaudhuri and U Dayal. An overview of data warehousing and OLAP technology. ACM SIGMOD Rec. 1997; 26, 65-74.

CY Chan and YE Ioannidis. Bitmap index design and evaluation. ACM SIGMOD Rec. 1998; 27, 355-66.

K Wu, A Shoshani and K Stockinger. Analyses of multi-level and multi-component compressed bitmap indexes. ACM Trans. Database Syst. 2010; 35, 1-52.

K Kambatla, G Kollias, V Kumar and A Grama. Trends in big data analytics. J. Parallel Distr. Comput. 2014; 74, 2561-73.

X Wu, X Zhu, GQ Wu and W Ding. Data mining with big data. IEEE Trans. Knowl. Data Eng. 2014; 26, 97-107.

K Stockinger and K Wu. Bitmap indices for data warehouses. Data Warehouses OLAP Concepts Architect. Solut. 2007; 1, 157-78.

ZQ Abdulhadi, Z Zuping and HI Housien. Bitmap index as effective indexing for low cardinality column in data warehouse. Int. J. Comput. Appl. 2013; 68, 38-42.

LJ Gosink, K Wu, EW Bethel, JD Owens and KI Joy. 2008, Bin- Hash Indexing: A Parallel Method for Fast Query Processing, Technical Report. Laurence Berkeley National Laboratories, USA.

Y Mei, K Ji and F Wang. A survey on bitmap index technologies for large-scale data retrieval. In: Proceedings of 2013 6th International Conference on Intelligent Networks and Intelligent Systems, Shenyang, China, 2013, p. 316-9.

Z Chen, Y Wen, J Cao, W Zheng, J Chang, Y Wu, G Ma, M Hakmaoui and G Peng. A survey of bitmap index compression algorithms for big data. Tsinghua Sci. Tech. 2015; 20, 100-15.

PO Neil and D Quass. Improved query performance with variant indexes. ACM SIGMOD Rec. 1997; 26, 38-49.

CY Chan and YE Ioannidis. An efficient bitmap encoding scheme for selection queries. ACM SIGMOD Rec. 1999; 28, 215-26.

M Stabno and R Wrembel. RLH: Bitmap compression technique based on run-length and huffman encoding. Inform. Syst. 2009; 34, 400-14.

S Kim, J Lee, SR Satti and B Moon. SBH: Super byte-aligned hybrid bitmap compression. Inform. Syst. 2016; 62, 155-68.

KL Wu and S Yu. Range-based bitmap indexing for high cardinality attributes with skew. In: Proceedings of the 22nd Annual International Computer Software and Applications Conference, Vienna, Austria, 1998, p. 61-6.

MC Wu and AP Buchmann. Encoded bitmap indexing for data warehouses. In: Proceedings of 14th International Conference on Data Engineering, Orlando, USA, 1998, p. 220-30.

S Vanichayobon, J Manfuekphan and L Gruenwald. Scatter bitmap: Space-time efficient bitmap indexing for equality and membership queries. In: Proceedings of 2006 IEEE Conference on Cybernetics and Intelligent Systems, Bangkok, Thailand, 2006, p. 1-6.

W Weahama, S Vanichayobon and J Manfuekphan. Using data clustering to optimize scatter bitmap index for membership queries. In: Proceedings of 2009 International Conference on Computer and Automation Engineering, Bangkok, Thailand, 2009, p. 174-8.

N Wattanakitrungroj and S Vanichayobon. Dual bitmap index: Space-time efficient bitmap index for equality and membership queries. In: Proceedings of 2006 International Symposium on Communications and Information Technologies, Bangkok, Thailand, 2006, p. 568-73.

GR Alam, MY Arafat, M Kamal and U Iftekhar. A new approach of dynamic encoded bitmap indexing technique based on query history. In: Proceedings of 5th International Conference on Electrical and Computer Engineering, Dhaka, Bangladesh, 2008, p. 974-9.

J Sainui, S Vanichayobon and N Wattanakitrungroj. Optimizing encoded bitmap index using frequent itemsets mining. In: Proceedings of 2008 International Conference on Computer and Electrical Engineering, Phuket, Thailand, 2008, p. 511-5.

A Keawpibal, N Wattanakitrungroj and S Vanichayobon. Enhanced encoded bitmap index for equality query. In: Proceedings of the 8th International Conference on Computing Technology and Information Management, Seoul, South Korea, 2012, p. 293-8.

N Keawpibal, J Duangsuwan, W Wettayaprasit, L Preechaveerakul and S Vanichayobon. DistEQ: Distributed equality query processing on encoded bitmap index. In: Proceedings of the 12th International Joint Conference on Computer Science and Software Engineering, Songkhla, Thailand, 2015, p. 309-14.

TPC-H: A Decision Support Benchmark. Available at: http://www.tpc.org/tpch, accessed November 2017.

Downloads

Published

2018-03-26

How to Cite

KEAWPIBAL, N., PREECHAVEERAKUL, L., & VANICHAYOBON, S. (2018). Optimizing Range Query Processing for Dual Bitmap Index. Walailak Journal of Science and Technology (WJST), 16(2), 133–142. https://doi.org/10.48048/wjst.2019.4146