Publications
Detailed Information
An Improved Bitmap Index Compression Scheme : 향상된 비트맵 인덱스 압축 기술
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Srinivasa Rao Satti | - |
dc.contributor.author | 김상철 | - |
dc.date.accessioned | 2017-07-14T02:58:20Z | - |
dc.date.available | 2017-07-14T02:58:20Z | - |
dc.date.issued | 2015-02 | - |
dc.identifier.other | 000000024748 | - |
dc.identifier.uri | https://hdl.handle.net/10371/123116 | - |
dc.description | 학위논문 (석사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2015. 2. Srinivasa Rao Satti. | - |
dc.description.abstract | Bitmap indexes are commonly used in most data warehousing applications such as on-line analytical processing. By storing the bitmaps in compressed form, these have been shown to be efficient not only for low cardinality attributes, as conventional wisdom would suggest, but also for high cardinality attributes. Compressed bitmap indexes, such as Byte-aligned Bitmap Compression (BBC), Word-Aligned Hybrid (WAH) and several of their variants have been shown to be efficient in terms of both time and space, compared to traditional database indexes.
In this thesis, we propose a new scheme called Super Byte-aligned Hybrid (SBH) bitmap compression. It is byte-based scheme that helps to reduce the space and uses the bucket to speed up the query processing time. The query processing time of SBH is up to five times faster than that of WAH, while the size of compressed bitmap indexes is retained nearly close to that of BBC. Thus, our scheme improves upon both these schemes. In addition, we implemented a data structure that combines B-tree and bitmap indexes. The performance of the data structure is evaluated by comparing with the Multi-resolution bitmap indexes, and we confirm the efficiency of the data structure. | - |
dc.description.tableofcontents | Abstract i
Contents ii List of Figures iv List of Tables vi Chapter 1 Introduction 1 1.1 Research in Bitmap Index Compression 3 1.2 Data Structure for using Bitmap Indexes 4 1.3 Contribution 4 1.4 Thesis Roadmap 5 Chapter 2 Related Work 6 2.1 Byte-aligned Bitmap Code (BBC) 7 2.2 Word-Aligned Hybrid (WAH) 10 2.3 Enhanced Word-Aligned Hybrid (EWAH) 10 2.4 Multi-resolution Bitmap Indexes 11 Chapter 3 Super Byte-aligned Hybrid (SBH) 13 3.1 Compression 13 3.2 Decompression 16 Chapter 4 Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes (BBBI) 19 4.1 Problem Definition 19 4.2 Sub-optimal Solution 20 4.3 Optimal Solution 20 Chapter 5 Experimental Results 22 5.1 Settings 23 5.2 Data Sets 23 5.2.1 Synthetic Data 24 5.2.2 TPC(H) Benchmark 24 5.2.3 Weather 26 5.3 Results 27 5.3.1 Super Byte-aligned Hybrid 27 5.3.2 Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes 34 Chapter 6 Conclusions 41 6.1 Summary 42 6.1.1 Super Byte-aligned Hybrid 42 6.1.2 Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes 42 6.2 Future Work 42 요약 47 | - |
dc.format | application/pdf | - |
dc.format.extent | 2402488 bytes | - |
dc.format.medium | application/pdf | - |
dc.language.iso | ko | - |
dc.publisher | 서울대학교 대학원 | - |
dc.subject | 비트맵 인덱스 | - |
dc.subject | 비트맵 압축 | - |
dc.subject | 자료구조 | - |
dc.subject.ddc | 621 | - |
dc.title | An Improved Bitmap Index Compression Scheme | - |
dc.title.alternative | 향상된 비트맵 인덱스 압축 기술 | - |
dc.type | Thesis | - |
dc.contributor.AlternativeAuthor | Sangchul Kim | - |
dc.description.degree | Master | - |
dc.citation.pages | vi, 47 | - |
dc.contributor.affiliation | 공과대학 전기·컴퓨터공학부 | - |
dc.date.awarded | 2015-02 | - |
- Appears in Collections:
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.