| Introduction | p. 1 |
| Goals | p. 2 |
| Outline | p. 3 |
| State of the Art of Data Warehouse Research | p. 5 |
| Introduction | p. 5 |
| Traditional Transaction-Oriented Systems | p. 5 |
| Data Warehouses for Decision Support | p. 7 |
| OLAP Vs. OLTP | p. 9 |
| Accelerating Query Speed | p. 10 |
| Denormalized Schemas | p. 10 |
| Materialized Views | p. 11 |
| No Locking | p. 13 |
| On-line Aggregation | p. 13 |
| Index Structures | p. 14 |
| Summary | p. 14 |
| Data Storage and Index Structures | p. 15 |
| Introduction | p. 15 |
| Memory Hierarchy | p. 15 |
| Mechanics of Disks | p. 16 |
| Data Space and Queries | p. 18 |
| Data Space | p. 18 |
| Queries | p. 18 |
| Tree-Based Indexing | p. 19 |
| Top-Down, Bottom-Up, and Bulk Loading | p. 20 |
| Point Quadtrees | p. 21 |
| kd-tree | p. 22 |
| kdb-tree | p. 22 |
| R-tree | p. 23 |
| R*-tree | p. 23 |
| Other Relatives of the R-tree Family and Other Tree Structures | p. 24 |
| Generic Tree Structures | p. 27 |
| Bitmap Indexing | p. 27 |
| Standard Bitmap Indexing | p. 27 |
| Multi-component Equality Encoded Bitmap Index | p. 29 |
| Range-Based Encoding | p. 31 |
| Multi-component Range-Based Encoding | p. 32 |
| Other Compression Techniques / Combination of Bitmaps and Trees | p. 33 |
| Arrays | p. 34 |
| Summary | p. 34 |
| Mixed Integer Problems for Finding Optimal Tree-Based Index Structures | p. 35 |
| Introduction | p. 35 |
| Optimization Problem Parameters | p. 35 |
| Mapping into a Mixed Integer Problem | p. 36 |
| Problem Complexity | p. 38 |
| Model Evaluation | p. 39 |
| Summary | p. 41 |
| Aggregated Data in Tree-Based Index Structures | p. 43 |
| Introduction | p. 43 |
| "Fit for Aggregation" Access Method | p. 47 |
| Materialization of Data | p. 48 |
| Modified Operations | p. 50 |
| Insert Operation | p. 51 |
| Delete Operation | p. 51 |
| Update Operation | p. 51 |
| Creating Index Structures, Bottom-Up Index Structures | p. 51 |
| Point Query Algorithm | p. 52 |
| Range Query Algorithm | p. 52 |
| Storage Cost | p. 52 |
| Height of Tree | p. 55 |
| Overlaps of Regions | p. 55 |
| Experiments | p. 56 |
| Cost Model | p. 57 |
| Physical Index Structure | p. 57 |
| Implementation | p. 58 |
| Generation of Test Data | p. 58 |
| Query Profile | p. 59 |
| Results of Experiments | p. 60 |
| Summary | p. 62 |
| Performance Models for Tree-Based Index Structures | p. 63 |
| Introduction | p. 63 |
| Fit for Modeling | p. 63 |
| Performance Models for Access Leaf Nodes | p. 64 |
| GRID Model | p. 64 |
| SUM Model | p. 66 |
| Equivalence of GRID Model and SUM Model | p. 68 |
| FRACTAL Model | p. 69 |
| Equivalence between FRACTAL Model, SUM Model, and GRID Model | p. 71 |
| PISA Model | p. 72 |
| Computational Efficiency of SUM Model and PISA Model | p. 75 |
| Adapting PISA Model to Different Distributions | p. 77 |
| Uniformly Distributed Data | p. 77 |
| Skewed Data | p. 78 |
| Normally Distributed Data | p. 80 |
| Model Evaluation | p. 81 |
| Uniformly Distributed Data | p. 81 |
| Skewed Data | p. 83 |
| Normally Distributed Data | p. 83 |
| PISA Model for Dependent Data | p. 85 |
| Extension of Models | p. 86 |
| Applications of Models | p. 87 |
| Savings of R*a-tree Depending on the Query Box Size and Form | p. 87 |
| Savings of R*a-tree Depending on the Number of Dimensions | p. 87 |
| Summary | p. 88 |
| Techniques for Comparing Index Structures | p. 91 |
| Introduction | p. 91 |
| Experimental Parameters | p. 91 |
| Data Specific Parameters | p. 91 |
| Query Specific Parameters | p. 92 |
| System Specific Parameters | p. 93 |
| Disk Specific Parameters | p. 93 |
| Configuration | p. 94 |
| Index Structures and Time Estimators | p. 95 |
| Time Measures for Tree-Based Index Structures | p. 95 |
| Time Measures for Bitmap Indexing Techniques | p. 97 |
| Classification Trees | p. 98 |
| Applied Methods | p. 99 |
| Value Sets of Parameters | p. 100 |
| Results | p. 101 |
| Statistics in Two Dimensions | p. 103 |
| Sum Aggregation | p. 104 |
| Median Aggregation | p. 105 |
| Count Aggregation | p. 105 |
| Results | p. 106 |
| Summary | p. 109 |
| Conclusion and Outlook | p. 113 |
| List of Symbols | p. 117 |
| Approximation of PISA Model | p. 123 |
| Bibliography | p. 125 |
| Index | p. 131 |
| Table of Contents provided by Publisher. All Rights Reserved. |
