Thesis
Workload-driven bitmap recompression for real-time query acceleration
Washington State University
Master of Science (MS), Washington State University
2013
Handle:
https://hdl.handle.net/2376/102388
Abstract
Modern large-scale applications are often required to process or producing large amounts of data. In an effort to speed up data analysis, databases often use bitmap indices. These indices have become widely adopted due to their dual properties of being able to leverage fast bit-wise operations for query processing and compressibility. Today, there are two popular bitmap compression schemes that employ a variation of run-length encoding, aligned over bytes (BBC) and words (WAH), respectively. While BBC typically offers high compression ratios, WAH can achieve faster query processing, but often at the cost of space. The third method, Variable Length Compression(VLC) is recently introduced with variable encoding scheme in an effort to achieve the best compression characteristics in both BBC and WAH. However, VLC sometimes falls short due to its greatest common divisor (GCD) computation for the different encoding lengths of columns and thus present an opportunity for improvement. In this thesis, we will introduce our enhanced algorithms based on VLC framework, Workload-Driven Bitmap Recompression for Real-Time Query Acceleration, in which we will describe three algorithms to achieve compression solution closer to optimal in both - high compression ratio and fast query.
Metrics
28 File views/ downloads
13 Record Views
Details
- Title
- Workload-driven bitmap recompression for real-time query acceleration
- Creators
- Fredton Doan
- Contributors
- David Chiu (Degree Supervisor)
- Awarding Institution
- Washington State University
- Academic Unit
- Electrical Engineering and Computer Science, School of
- Theses and Dissertations
- Master of Science (MS), Washington State University
- Publisher
- Washington State University; [Pullman, Washington] :
- Identifiers
- 99900525030401842
- Language
- English
- Resource Type
- Thesis