| DEDICATION | 第6-7页 |
| Abstract | 第7-8页 |
| LIST OF FIGURES | 第11-13页 |
| LIST OF TABLES | 第13-14页 |
| CHAPTER 1:INTRODUCTION | 第14-34页 |
| 1.1 Overview of Decision Support Systems | 第15页 |
| 1.2 Data Warehouses and OLAP:Basic Concepts | 第15-21页 |
| 1.2.1 Online Analytical Processing | 第16页 |
| 1.2.2 Data Warehouses | 第16-21页 |
| 1.3 Indexing Techniques for Data Warehouses | 第21-25页 |
| 1.3.1 Multidimensional Array-Based Techniques | 第21页 |
| 1.3.2 B-Tree Based Multidimensional Indexing Techniques | 第21-22页 |
| 1.3.3 Hierarchical Indexing Techniques | 第22-23页 |
| 1.3.4 Projection Index | 第23页 |
| 1.3.5 Bitmap Indexing Techniques | 第23-25页 |
| 1.4 Variations of Bitmap Indices | 第25-31页 |
| 1.4.1 Basic Bitmap Index | 第25-26页 |
| 1.4.2 Encoding-Based Bitmap Indexes | 第26-29页 |
| 1.4.3 Bit-Sliced Index | 第29-30页 |
| 1.4.4 Join Index | 第30-31页 |
| 1.5 Bitmap Indexes Supported by Commercial DMBS Products | 第31-32页 |
| 1.6 Motivation and Contribution of the Thesis | 第32页 |
| 1.7 Outline of the Thesis | 第32-34页 |
| CHAPTER 2:PERFORMANCE OF BITMAP INDEXES FOR HIGH-CARDINALITY ATTRIBUTES | 第34-50页 |
| 2.1 Background | 第34-35页 |
| 2.2 Low-Cardinality Attributes vs.High-Cardinality Attributes | 第35-36页 |
| 2.3 Compression Techniques for Bitmap Indices | 第36-41页 |
| 2.3.1 BBC Bitmap Compression Scheme | 第36-38页 |
| 2.3.2 WAH Bitmap Compression Scheme | 第38-41页 |
| 2.4 Compressed Sizes of Bitmap Indices | 第41-46页 |
| 2.4.1 The Counting Groups | 第41-43页 |
| 2.4.2 Sizes of Random Bitmaps | 第43-45页 |
| 2.4.3 Sizes of WAH Compressed Bitmap Indices | 第45-46页 |
| 2.5 Binning | 第46-48页 |
| 2.6 Bitmap Index Tuning | 第48-50页 |
| CHAPTER 3:IMPROVING BITMAP INDICES COMPRESSION BY DATA REORDERING | 第50-55页 |
| 3.1 The Proposed Strategy | 第50-51页 |
| 3.2 Improving Bitmap Compression by Tuple Reordering | 第51-54页 |
| 3.2.1 Problem Formulation | 第51-53页 |
| 3.2.2 Reduction to the Traveling Salesperson Problem | 第53-54页 |
| 3.3 Limitations of the Proposed Strategy | 第54-55页 |
| CHAPTER 4:EXPERIMENTAL RESULTS | 第55-64页 |
| 4.1 Experiment Environment:FastBit | 第55-56页 |
| 4.2 Performance of the Proposed Strategy | 第56-64页 |
| 4.2.1 Index Size | 第56-61页 |
| 4.2.2 Query Response Time | 第61-64页 |
| CHAPTER 5:CONCLUSIONS AND FUTURE WORK | 第64-66页 |
| REFERENCES | 第66-70页 |
| ACKNOWLEDGEMENTS | 第70-71页 |
| 附录A:详细中文摘要 | 第71-73页 |
| APPENDIX B:PUBLISHED PAPER | 第73-78页 |
