Introduction / 1: |
Goals / 1.1: |
Outline / 1.2: |
State of the Art of Data Warehouse Research / 2: |
Traditional Transaction-Oriented Systems / 2.1: |
Data Warehouses for Decision Support / 2.3: |
OLAP Vs. OLTP / 2.4: |
Accelerating Query Speed / 2.5: |
Denormalized Schemas / 2.5.1: |
Materialized Views / 2.5.2: |
No Locking / 2.5.3: |
On-line Aggregation / 2.5.4: |
Index Structures / 2.5.5: |
Summary / 2.6: |
Data Storage and Index Structures / 3: |
Memory Hierarchy / 3.1: |
Mechanics of Disks / 3.3: |
Data Space and Queries / 3.4: |
Data Space / 3.4.1: |
Queries / 3.4.2: |
Tree-Based Indexing / 3.5: |
Top-Down, Bottom-Up, and Bulk Loading / 3.5.1: |
Point Quadtrees / 3.5.2: |
kd-tree / 3.5.3: |
kdb-tree / 3.5.4: |
R-tree / 3.5.5: |
R*-tree / 3.5.6: |
Other Relatives of the R-tree Family and Other Tree Structures / 3.5.7: |
Generic Tree Structures / 3.5.8: |
Bitmap Indexing / 3.6: |
Standard Bitmap Indexing / 3.6.1: |
Multi-component Equality Encoded Bitmap Index / 3.6.2: |
Range-Based Encoding / 3.6.3: |
Multi-component Range-Based Encoding / 3.6.4: |
Other Compression Techniques / Combination of Bitmaps and Trees / 3.6.5: |
Arrays / 3.7: |
Mixed Integer Problems for Finding Optimal Tree-Based Index Structures / 3.8: |
Optimization Problem Parameters / 4.1: |
Mapping into a Mixed Integer Problem / 4.3: |
Problem Complexity / 4.4: |
Model Evaluation / 4.5: |
Aggregated Data in Tree-Based Index Structures / 4.6: |
"Fit for Aggregation" Access Method / 5.1: |
Materialization of Data / 5.3: |
Modified Operations / 5.4: |
Insert Operation / 5.4.1: |
Delete Operation / 5.4.2: |
Update Operation / 5.4.3: |
Creating Index Structures, Bottom-Up Index Structures / 5.4.4: |
Point Query Algorithm / 5.4.5: |
Range Query Algorithm / 5.4.6: |
Storage Cost / 5.5: |
Height of Tree / 5.6: |
Overlaps of Regions / 5.7: |
Experiments / 5.8: |
Cost Model / 5.8.1: |
Physical Index Structure / 5.8.2: |
Implementation / 5.8.3: |
Generation of Test Data / 5.8.4: |
Query Profile / 5.8.5: |
Results of Experiments / 5.8.6: |
Performance Models for Tree-Based Index Structures / 5.9: |
Fit for Modeling / 6.1: |
Performance Models for Access Leaf Nodes / 6.3: |
GRID Model / 6.3.1: |
SUM Model / 6.3.2: |
Equivalence of GRID Model and SUM Model / 6.3.3: |
FRACTAL Model / 6.3.4: |
Equivalence between FRACTAL Model, SUM Model, and GRID Model / 6.3.5: |
PISA Model / 6.4: |
Computational Efficiency of SUM Model and PISA Model / 6.5: |
Adapting PISA Model to Different Distributions / 6.6: |
Uniformly Distributed Data / 6.6.1: |
Skewed Data / 6.6.2: |
Normally Distributed Data / 6.6.3: |
PISA Model for Dependent Data / 6.7: |
Extension of Models / 6.9: |
Applications of Models / 6.10: |
Savings of R*a-tree Depending on the Query Box Size and Form / 6.10.1: |
Savings of R*a-tree Depending on the Number of Dimensions / 6.10.2: |
Techniques for Comparing Index Structures / 6.11: |
Experimental Parameters / 7.1: |
Data Specific Parameters / 7.2.1: |
Query Specific Parameters / 7.2.2: |
System Specific Parameters / 7.2.3: |
Disk Specific Parameters / 7.2.4: |
Configuration / 7.2.5: |
Index Structures and Time Estimators / 7.3: |
Time Measures for Tree-Based Index Structures / 7.3.1: |
Time Measures for Bitmap Indexing Techniques / 7.3.2: |
Classification Trees / 7.4: |
Applied Methods / 7.4.1: |
Value Sets of Parameters / 7.4.2: |
Results / 7.4.3: |
Statistics in Two Dimensions / 7.5: |
Sum Aggregation / 7.5.1: |
Median Aggregation / 7.5.2: |
Count Aggregation / 7.5.3: |
Conclusion and Outlook / 7.5.4: |
List of Symbols / A: |
Approximation of PISA Model / B: |
Bibliography |
Index |
Introduction / 1: |
Goals / 1.1: |
Outline / 1.2: |
State of the Art of Data Warehouse Research / 2: |
Traditional Transaction-Oriented Systems / 2.1: |
Data Warehouses for Decision Support / 2.3: |