GPU-PLWAH: GPU-based implementation of the PLWAH algorithm for compressing bitmaps

• Autorzy: Andrzejewski W. , Wrembel R.
• Języki publikacji: EN

Abstrakty

EN

Bitmap indexes are data structures applied to index- ing attributes in databases and data warehouses. A drawback of a bitmap index is that its size increases when the domain of an indexed attribute increases. As a consequence, for wide domains, the size of a bitmap index is too large to be efficiently processed. Hence, various techniques of compressing bitmap indexes have been proposed. A compression technique incurs some system overhead (mainly CPU) for compression and decompression operations. For this reason, we propose to use additional processing power of graphical processing units (GPUs). In this paper, we present the GPU-PLWAH algorithm that is a parallel implementation of the recently developed PLWAH compression algorithm. GPU-PLWAH was experimentally compared to its traditional CPU version as well as to our previously developed parallel GPU implementation of the WAH compression algorithm. The experiments show that applying GPUs significantly reduces compression/decompression time.

Słowa kluczowe

EN

data warehouse; GPGPU; bitmap index; bitmap index compression; PLWAH; WAH

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2011
• Tom: Vol. 40, no 3
• Strony: 627--650
• Opis fizyczny: Bibliogr. 30 poz., wykr.

Twórcy

autor

Andrzejewski W.

autor

Wrembel R.

• Poznan University of Technology, Institute of Computing Science Pl. Marii Skłodowskiej-Curie 5, Poznań, Poland,

Bibliografia

• Andrzejewski, W. (2007) Fast K-Medoids Clustering on PCs. Proc. of the ADMKD Workshop. Technical University of Varna, 29-44.
• Andrzejewski, W. and Wrembel, R. (2010) GPU-WAH: Applying GPUs to compressing bitmap indexes with word aligned hybrid. Proc. of Int. Conference on Database and Expert Systems Applications (DEXA). LNCS 6262, Springer, 315-329.
• Antoshenkov, G. and Ziauddin, M. (1996) Query processing and optimization in Oracle RDB. VLDB Journal 5(4), 229-237.
• Böhm, C., Noll, R., Plant, C. and Wackersreuther, B. (2009) Density-based clustering Rusing graphics processors. Proc. of ACM SIGMOD Int. Conference on Information and Knowledge Management (CIKM). ACM Press, 661-670.
• Cao, F., Tung, A.K.H. and Zhou, A. (2006) Scalable clustering Rusing graphics processors. Advances in Web-Age Information Management. LNCS 4016, Springer, 372-384.
• Chen, S., Zhao, J., Qin, J. and Heng, P.-A. (2009) An efficient sorting algorithm with CUDA. Journal of the Chinese Institute of Engineers 32 (7), 915-921.
• Deliège, F. (2009) Concepts and Techniques for Flexible and Effective Music Data Management. PhD Thesis, Aalborg University, Denmark.
• Erra, U. (2005) Toward real time fractal image compression using graphics hardware. Proc. of Advances in Visual Computing. LNCS 3804, Springer, 723-728.
• Govindaraju, N., Gray, J., Kumar, R. and Manocha, D. (2006) GPU- TeraSort: high performance graphics co-processor sorting for large database management. Proc. of ACM SIGMOD Int. Conf. on Manage- ment of Data. ACM Press, 325-336.
• Govindaraju, N., Lloyd, B., Wang, W., Lin, M., and Manocha, D. (2004) Fast computation of database operations using graphic processors. Proc. of ACM SIGMOD Int. Conference on Management of Data. ACM Press, 215-226.
• Greß, A. and Zachmann, G. (2006) GPU-ABiSort: Optimal Parallel Sorting on Stream Architectures. Proc. of the IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE Computer Society.
• Harris, M., Sengupta, S. and Owens, J.D. (2007) Parallel prefix sum (scan) with CUDA. GPU Gems 3. Addison Wesley, 851-875.
• Huffman, D.A. (1952) A method for the construction of minimum-redundancy codes. Proc. of the Institute of Radio Engineers. The Institute of Radio Engineers Inc., 1098-1101.
• Lehman, T.J. and Carey, M.J. (1986) A study of index structures for main memory database management systems. Proc. of Int. Conference on Very Large Databases (VLDB). Morgan Kaufmann, 294-303.
• Nourani, M. and Tehranipour, M.H. (2005) RL-Huffman encoding for test compression and power reduction in scan applications. ACM Transactions on Design Automation of Electronic Systems 10 (1), 91-115.
• NVidia1 (2010) NVIDIA CUDA C Programming Best Practices Guide. NVIDIA CUDA C Toolkit 2.3.
• NVidia2 (2010) NVIDIA’s Next Generation CUDA Compute Architecture: Fermi. White Paper, NVIDIA.
• O’Neil, P. and Quass, D. (1997) Improved query performance with variant indexes. Proc. of ACM SIGMOD Int. Conference on Management of Data. ACM Press, 38-49.
• O’Neil, E., O’Neil, P. and Wu, K. (2007) Bitmap index design choices and their performance implications. Research Report No. 62756, Lawrence Berkeley National Laboratory.
• Sathish, N., Harris, M. and Garlang, M. (2009) Designing efficient sorting algorithms for manycore GPUs. Proc. of the IEEE International Parallel & Distributed Processing Symposium. IEEE Computer Society, 1-10.
• Sengupta, S., Harris, M., Zhang, Y. and Owens, J.D. (2007) Scan primitives for GPU computing. Proc. of the Graphics Hardware 2007 Conference. ACM Press, 97-106.
• Shalom, S.A.A., Dash, M. and Minh, T. (2008) Efficient K-Means Clustering Using Accelerated Graphics Processors. Proc. of Int. Conference on Data Warehousing and Knowledge Discovery (DaWaK) LNCS 5182, Springer, 166-175.
• Stabno, M. and Wrembel, R. (2009) RLH: Bitmap Compression technique based on runlength and Huffman encoding. Information Systems 34 (4-5), 400-414.
• Stockinger, K. and Wu, K. (2007) Bitmap indices for data warehouses In: R. Wrembel and C. Koncilla, eds., Data warehouses and OLAP: Concepts, Architectures and Solutions. Idea Group Inc., 157-178.
• Wu, K., Otoo, E.J., and Shoshani, A. (2002) Compressing bitmap indexes for faster serach operations. Proc. of the Int. Conference on Scientific and Statistical Database Management (SSDBM). IEEE Computer Society, 99-108.
• Wu, K., Otoo, E.J. and Shoshani, A. (2004a) An efficient compression scheme for bitmap indices. Research Report No. 49626, Lawrence Berkeley National Laboratory.
• Wu, K., Otoo, E.J. and Shoshani, A. (2004b) On the performance of bitmap indices for high cardinality attributes. Proc. of Int. Conference on Very Large Data Bases (VLDB). VLDB Endowment, 24-35.
• Wu, K., Otoo, E.J. and Shoshani, A. (2006) Optimizing bitmap indices with efficient compresion. ACM Transactions on Database Systems (TODS) 31 (1), 1-38.
• Wu, M. and Buchmann, A. (1998) Encoded Bitmap indexing for data warehouses. Proc. of Int. Conference on Data Engineering (ICDE). IEEE Computer Society, 220-230.
• Zaker, M., Phon-Amnuaisuk, S. and Haw, S. (2008) An adequate design for large data warehouse systems: Bitmap index versus b-tree index. International Journal of Computers and Communications 2 (2), 39-46.