Comprehensive Analysis and Comparative Evaluation of Bitmap Indexing Methods for Efficient Data Management

Authors

  • D. Pratima Research Scholar, Department of CSE, Koneru Lakshmaiah Education Foundation, Green Fields, Vaddeswaram, Andhra Pradesh, India.
  • MD. Moulana Professor, Department of CSE, Koneru Lakshmaiah Education Foundation, Green Fields, Vaddeswaram, Andhra Pradesh, India.

Keywords:

Bitmap indexing, Roaring bitmaps, SIMD-based indexing

Abstract

This review paper provides an in-depth analysis of various bitmap indexing methods and their applications in data management systems. We explore traditional bitmap indexing, compressed bitmap indexing, Roaring bitmaps, and SIMD-based indexing. For each method, we discuss their principles, data structures, algorithms, compression techniques, query performance, memory usage, scalability, and potential applications. We also highlight their strengths, limitations, and comparative analysis based on evaluation metrics. Additionally, we examine current research trends, ongoing efforts, research gaps, and potential future directions in bitmap indexing methods. The insights gained from this review will guide practitioners and researchers in selecting and implementing the most suitable bitmap indexing method for their data management needs.

Downloads

Download data is not yet available.

References

Wu, K., Otoo, E. J., & Shoshani, A. (2006). Compressing bitmap indexes for faster search operations. In Proceedings of the 32nd international conference on Very large data bases (pp. 115-126).

Lemire, D., & Boytsov, L. (2016). Decoding billions of integers per second through vectorization. Software: Practice and Experience, 46(8), 1159-1170.

Bressan, S., Aref, W. G., & Soares, C. (2001). Bitmap indexing for big data. ACM Transactions on Database Systems (TODS), 26(4), 1-40.

O'Neil, P., Quass, D., & O'Neil, E. (1997). The log-structured merge-tree (LSM-tree). Acta Informatica, 33(4), 351-385.

Guttman, A. (1984). R-trees: A dynamic index structure for spatial searching. In Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data (pp. 47-57).

Wu, K., &Otoo, E. J. (2005). Top-k query processing in bitmap indexes. ACM Transactions on Database Systems (TODS), 30(2), 532-567.

Boncz, P. A., Manegold, S., & Kersten, M. L. (2005). Database architecture optimized for the new bottleneck: memory access. In Proceedings of the 31st international conference on Very large data bases (pp. 705-716).

Silvestri, F., Venturini, R., & Metzler, D. (2010). Building compressed bitmap indexes for big data retrieval. ACM Transactions on Information Systems (TOIS), 28(1), 1-38.

Petri, M., Johnson, T., & Ross, K. A. (2019). Bit Magic: a fast C++11 framework for compressed bit sets. Software: Practice and Experience, 49(6), 1061-1079.

Abadi, D. J., Madden, S., & Ferreira, M. (2006). Integrating compression and execution in column-oriented database systems. In Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data (pp. 671-682).

Lemire, D., Kaser, O., &Aouiche, K. (2010). Sorting improves word-aligned bitmap indexes. Data & Knowledge Engineering, 69(1), 3-28.

Sidlauskas, D., & Jensen, C. S. (2015). Efficient range queries for compressed bitmap indexes. Information Systems, 49, 155-170.

Zhang, H., Zhang, Q., & Zhou, A. (2020). A comprehensive survey on bitmap index compression techniques. Future Generation Computer Systems, 110, 130-142.

Lu, Z., & Yu, J. X. (2013). Efficient compressed bitmap indexes for multilevel structural data. IEEE Transactions on Knowledge and Data Engineering, 25(7), 1636-1650.

Zhou, A., Wu, K., &Otoo, E. J. (2011). Compressing bitmap indexes by reordering and partitioning. ACM Transactions on Database Systems (TODS), 36(2), 1-40.

Aji, A. M., & Wang, F. (2014). Boosting the performance of bitmap indices through bitmap compression and partitioning. ACM Transactions on Database Systems (TODS), 39(2), 1-40.

Li, Y., Liu, K., & Feng, J. (2019). Exploiting bitwise parallelism in query processing on compressed bitmap indexes. Journal of Parallel and Distributed Computing, 130, 47-61.

Stoffel, K., & Lehner, W. (2013). Optimizing performance and storage space for compressed bitmap indexes. In Proceedings of the 25th International Conference on Scientific and Statistical Database Management (pp. 1-12).

O'Neil, P. (2011). Bitmap indexes: efficient data manipulation for read-mostly data warehouses. In High Performance Data Mining (pp. 149-168). Springer.

Fasiha, A. S., Eltabakh, M. Y., Ouzzani, M., & Osgood, N. (2014). Optimizing compressed bitmap indexes in big data systems. In Proceedings of the VLDB Endowment, 7(9), 697-708.

Idreos, S., Alagiannis, I., &Ailamaki, A. (2011). Adaptive indexing in modern database kernels. Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, 1189-1192.

Peng, Y., Zhang, J., Zhang, Y., & Shen, H. T. (2018). Incorporating bitmap index into deep neural networks for efficient data analytics. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2061-2069.

Kourtellis, N., Siganos, G., Rodriguez, P., Almeida, V., & Vahdat, A. (2013). Scalable and adaptive data indexing with bitmap indexes. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1315-1323.

Patil, A. ., & Govindaraj, S. K. . (2023). ADL-BSDF: A Deep Learning Framework for Brain Stroke Detection from MRI Scans towards an Automated Clinical Decision Support System. International Journal on Recent and Innovation Trends in Computing and Communication, 11(3), 11–23. https://doi.org/10.17762/ijritcc.v11i3.6195

Ólafur, J., Virtanen, M., Vries, J. de, Müller, T., & Müller, D. Data-Driven Decision Making in Engineering Management: A Machine Learning Framework. Kuwait Journal of Machine Learning, 1(1). Retrieved from http://kuwaitjournals.com/index.php/kjml/article/view/108

Downloads

Published

21.09.2023

How to Cite

Pratima, D. ., & Moulana, M. . (2023). Comprehensive Analysis and Comparative Evaluation of Bitmap Indexing Methods for Efficient Data Management. International Journal of Intelligent Systems and Applications in Engineering, 11(4), 563–571. Retrieved from https://ijisae.org/index.php/IJISAE/article/view/3591

Issue

Vol. 11 No. 4 (2023)

Section

Research Article

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.

IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.