Universiẗat, Diss., 2001--Bonn.

Techn. University, Diss., 2003--Berlin.

University, Diss., 2004--Konstanz.

Zugl.: Erlangen, Nürnberg, University, Diss., 2009.

Zugl.: Rostock, Univ., Diss., 2008

University, Diss., 2000--Freiburg (Breisgau).

Techn. University, Diss., 2004--Berlin.

Universiẗat, Diss., 2005--Tübingen.

In-memory column-store database systems have to keep base data as well as generated intermediate results during query processing in main memory. Moreover, base data as well as intermediate results are usually represented as integer data in this kind of database systems. Therefore, the effort to access intermediate results is equivalent to the effort to access the base data. Based on this characteristic, the optimization of intermediate results is an interesting general optimization knob and has a high impact on the performance of the query processing. In this direction, we propose the continuous use of integer compression methods for intermediate results and design a novel compression-aware query processing concept. To minimize the overall query execution time, the best-fitting integer compression scheme has to be used. However and as shown in the literature, there is no single-best integer compression algorithm --- data and hardware characteristics as well as the optimization objectives like decompression speed or compression rate determine the properties of fitting algorithms. To systematically tackle this challenge from a system perspective, we present our vision of a model-based approach to make a large corpus of integer compression schemes available in our compression-aware query processing concept. Then, we describe in detail our model-based approach by (i) introducing our developed metamodel for integer compression schemes called COLLATE and by (ii) showing that a large corpus of integer compression schemes can be described as a model conforming with COLLATE. Afterwards, we introduce a concept and an implementation to automatically derive scalar compression and decompression routines out of model compression schema. Finally, we propose a novel generalized SIMD concept for integer compression algorithms called BOUNCE to adapt a scalar execution to a data parallel execution using SIMD instruction set extensions of general-purpose CPUs.:1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1. Thesis Goals and Contributions . . . . . . . . . . . . . . . . . .7 1.1.1. Model-Based Concept for Compression Schemes . . . . . . . . . . 8 1.1.2. Model-Based Generator Framework . . . . . . . . . . . . . . . .10 1.1.3. Generalized SIMD Concept for Integer Compression . . . . . . . 12 1.2. Impact of Thesis Contributions . . . . . . . . . . . . . . . . . 14 1.2.1. Publications of Thesis Contribution . . . . . . . . . . . . . .14 1.2.2. Open Source Contributions . . . . . . . . . . . . . . . . . . .17 1.2.3. Additional Contributions . . . . . . . . . . . . . . . . . . . 18 1.3. Structure of the Thesis . . . . . . . . . . . . . . . . . . . . .21 I. Model-Based Concept for Compression Schemes . . . . . . . . . . . 23 2. Compression-Aware In-Memory Query Processing . . . . . . . . . . .25 2.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.1. Vision of Compression-Aware In-Memory Query Processing . . . . 26 2.1.2. System Design Challenge for Compression-Aware Processing . . . 26 2.1.3. Our Contribution and Outline . . . . . . . . . . . . . . . . . 27 2.2. System Design Overview . . . . . . . . . . . . . . . . . . . . . 28 2.3. Survey of Lightweight Data Compression Algorithms . . . . . . . .29 2.3.1. Analysis of Basic Lightweight Compression Techniques . . . . . 29 2.3.2. Analysis of Lightweight Compression Algorithms . . . . . . . . 30 2.3.3. Derived System Description and Properties . . . . . . . . . . .31 2.4. COLLATE Model . . . . . . . . . . . . . . . . . . . . . . . . . .32 2.5. Transformation of Model Instances . . . . . . . . . . . . . . . .34 2.5.1. Model Instances for Byte-oriented Encoding Algorithms . . . . .34 2.5.2. Transformation to Executable Code . . . . . . . . . . . . . . .35 2.6. Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . .38 2.6.1. Structural Aspect . . . . . . . . . . . . . . . . . . . . . . .39 2.6.2. Operational Aspect . . . . . . . . . . . . . . . . . . . . . . 39 2.6.3. Optimization Aspect . . . . . . . . . . . . . . . . . . . . . .40 2.7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3. Metamodeling Lightweight Data Compression Algorithms . . . . . . .41 3.1. Problem Statement . . . . . . . . . . . . . . . . . . . . . . . .41 3.2. Metamodeling Lightweight Compression Algorithms . . . . . . . . .43 3.2.1. Properties of Data Compression Algorithms . . . . . . . . . . .43 3.2.2. COLLATE Metamodel . . . . . . . . . . . . . . . . . . . . . . .44 3.2.3. Interaction of COLLATE Concepts . . . . . . . . . . . . . . . .46 3.3. Application Scenarios . . . . . . . . . . . . . . . . . . . . . .46 3.3.1. Algorithms as Models . . . . . . . . . . . . . . . . . . . . . 46 3.3.2. Compression Algorithm Language CoALa . . . . . . . . . . . . . 48 3.3.3. Transformation of CoALa Code to Executable Code . . . . . . . .49 3.4. Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.5. Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 II. Model-Based Generator Framework . . . . . . . . . . . . . . . . .55 4. LCTL: Lightweight Compression Template Library . . . . . . . . . .57 4.1. Problem Statement . . . . . . . . . . . . . . . . . . . . . . . .57 4.2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . .59 4.2.1. Characteristics of Lightweight Compression . . . . . . . . . . 59 4.2.2. Metamodel COLLATE . . . . . . . . . . . . . . . . . . . . . . .60 4.3. Lightweight Compression Template Library . . . . . . . . . . . . 62 4.3.1. Template Metaprogramming for Tree Transformations . . . . . . .62 4.3.2. Lightweight Compression Template Library . . . . . . . . . . . 64 4.4. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.4.1. Format Space Diversity . . . . . . . . . . . . . . . . . . . . 71 4.4.2. Compile-Times . . . . . . . . . . . . . . . . . . . . . . . . .72 4.4.3. Run-Times . . . . . . . . . . . . . . . . . . . . . . . . . . .73 4.5. Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . .73 4.5.1. Further Code Optimization . . . . . . . . . . . . . . . . . . .74 4.5.2. Format Selection . . . . . . . . . . . . . . . . . . . . . . . 74 4.5.3. Integration . . . . . . . . . . . . . . . . . . . . . . . . . .75 4.6. Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5. Integrating Compression into Apache Arrow . . . . . . . . . . . . 77 5.1. Problem Statement . . . . . . . . . . . . . . . . . . . . . . . .77 5.2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . .79 5.2.1. Apache Arrow . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.2.2. Lightweight Integer Compression . . . . . . . . . . . . . . . .82 5.2.3. Lessons Learned . . . . . . . . . . . . . . . . . . . . . . . .83 5.3. ArrowComp Framework . . . . . . . . . . . . . . . . . . . . . . .83 5.3.1. Metamodel for (De)Compression . . . . . . . . . . . . . . . . .84 5.3.2. Self-Describing Columns . . . . . . . . . . . . . . . . . . . .85 5.3.3. Implementation . . . . . . . . . . . . . . . . . . . . . . . . 86 5.4. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.4.1. Data Sizes . . . . . . . . . . . . . . . . . . . . . . . . . . 90 5.4.2. Run Times . . . . . . . . . . . . . . . . . . . . . . . . . . .90 5.5. Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 92 5.5.1. Storage-oriented Formats . . . . . . . . . . . . . . . . . . . 92 5.5.2. Processing-oriented Formats . . . . . . . . . . . . . . . . . .93 5.5.3. Apache Arrow-centric Work . . . . . . . . . . . . . . . . . . .93 5.6. Conclusion and Future Work . . . . . . . . . . . . . . . . . . . 94 III. Generalized SIMD Concept for Integer Compression . . . . . . . .95 6. Partition-Based SIMD Processing . . . . . . . . . . . . . . . . . 97 6.1. Problem Statement . . . . . . . . . . . . . . . . . . . . . . . .97 6.2. Gather Evaluation . . . . . . . . . . . . . . . . . . . . . . . .99 6.2.1. Evaluation Setup . . . . . . . . . . . . . . . . . . . . . . . 99 6.2.2. Evaluation Results . . . . . . . . . . . . . . . . . . . . . .101 6.3. Partition-based SIMD . . . . . . . . . . . . . . . . . . . . . .105 6.4. Application Use Cases . . . . . . . . . . . . . . . . . . . . . 106 6.4.1. Vectorized Query Processing . . . . . . . . . . . . . . . . . 107 6.4.2. Integer Compression . . . . . . . . . . . . . . . . . . . . . 109 6.5. Related Work . . . . . . . . . . . . . . . . . . . . . . . . . .110 6.6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . .111 7. BOUNCE: Memory-Efficient SIMD Compression . . . . . . . . . . . .113 7.1. Problem Statement . . . . . . . . . . . . . . . . . . . . . . . 113 7.2. Analyzing State-of-the-Art . . . . . . . . . . . . . . . . . . .115 7.2.1. Bitpacking . . . . . . . . . . . . . . . . . . . . . . . . . .116 7.2.2. Simple Algorithms . . . . . . . . . . . . . . . . . . . . . . 120 7.2.3. Varint Algorithms . . . . . . . . . . . . . . . . . . . . . . 122 7.2.4. Further Compression Algorithms . . . . . . . . . . . . . . . .124 7.2.5. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 7.3. BOUNCE: Block concurrent SIMD Concept . . . . . . . . . . . . . 126 7.4. BOUNCE Application . . . . . . . . . . . . . . . . . . . . . . .128 7.4.1. Application to BP . . . . . . . . . . . . . . . . . . . . . . 128 7.4.2. Application to Simple Algorithms . . . . . . . . . . . . . . .130 7.4.3. Application to Varint Algorithms . . . . . . . . . . . . . . .130 7.4.4. Application to Further Algorithms . . . . . . . . . . . . . . 130 7.5. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . .131 7.5.1. Evaluation Setup . . . . . . . . . . . . . . . . . . . . . . .131 7.5.2. Performance of the Data Access Pattern . . . . . . . . . . . .132 7.5.3. Evaluating Bitpacking . . . . . . . . . . . . . . . . . . . . 132 7.5.4. Synthetic Data Sets with Fixed Bit Widths . . . . . . . . . . 133 7.5.5. Synthetic Data Sets with Different Bit Widths . . . . . . . . 134 7.5.6. Impact of Different Hardware Architectures . . . . . . . . . .135 7.5.7. Evaluation on Real Data Sets . . . . . . . . . . . . . . . . .136 7.6. Related Work . . . . . . . . . . . . . . . . . . . . . . . . . .137 7.7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . .137 8. Conclusion and Research Outlook . . . . . . . . . . . . . . . . .139 8.1. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 8.2. Research Outlook . . . . . . . . . . . . . . . . . . . . . . . .140 / Spaltenorientierte InMemory Datenbanksysteme müssen sowohl Basisdaten als auch generierte Zwischenergebnisse während der Anfrageverarbeitung im Hauptspeicher halten. Darüber hinaus werden Basisddaten sowie auch Zwischenergebnisse in dieser Art von Datenbanksystemen normalerweise als Integerdaten repräsentiert. Daher ist der Aufwand für den Zugriff auf Zwischenergebnisse äquivalent zum Aufwand für den Zugriff auf die Basisdaten. Basierend auf dieser Eigenschaft ist die Optimierung von Zwischenergebnissen ein wichtiger genereller Optimierungsparameter und hat einen hohen Einfluss auf die Leistung der Anfrageausführung. Deshalb untersuchen wir die kontinuierliche Verwendung von Integerkompressionsschemata für Zwischenergebnisse und haben ein neues Anfrageverarbeitungskonzept entworfen, welches sich der Datenkompression zur Effizienzsteigerung bedient. Um die Gesamtanfrageausführungszeit zu minimieren, muss das am besten geeignete Integerkompressionsschema verwendet werden. Bisherige Untersuchungen haben jedoch erwiesen, dass es keinen allgemeinen besten Integerkompressionsalgorithmus gibt. Daten und Hardwaremerkmale sowie Optimierungsziele wie Dekompressionsgeschwindigkeit oder Kompressionsrate bestimmen die Eigenschaften passender Algorithmen. Um hier einen Lösungsansatz ausgehend von der Systemperspektive zu eröffnen, präsentieren wir in dieser Arbeit einen modellbasierten Ansatz, um eine große Anzahl von Integerkompressionsschemata in unserem kompressionsbewussten Anfrageverarbeitungskonzept verfügbar zu machen. Danach beschreiben wir im Detail unseren modellbasierten Ansatz, indem wir (i) unser entwickeltes Metamodell für Integerkompressionsschemata namens COLLATE vorstellen und (ii) zeigen, dass eine große Anzahl von Integerkompressionsschemata als Modell beschrieben werden kann, welches dem Ansatz von COLLATE entspricht. Danach stellen wir ein Konzept und eine Implementierung vor, um skalare Kompressions und Dekompressionsroutinen automatisch aus dem Kompressionsschemamodell abzuleiten. Schließlich stellen wir ein neuartiges generalisiertes SIMDKonzept für Integerkompressionsalgorithmen namens BOUNCE vor, um aus einer skalaren Ausführung eine datenparallele Ausführung unter Verwendung von SIMDBefehlssatzerweiterungen von allgemeinen CPUs abzuleiten.:1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1. Thesis Goals and Contributions . . . . . . . . . . . . . . . . . .7 1.1.1. Model-Based Concept for Compression Schemes . . . . . . . . . . 8 1.1.2. Model-Based Generator Framework . . . . . . . . . . . . . . . .10 1.1.3. Generalized SIMD Concept for Integer Compression . . . . . . . 12 1.2. Impact of Thesis Contributions . . . . . . . . . . . . . . . . . 14 1.2.1. Publications of Thesis Contribution . . . . . . . . . . . . . .14 1.2.2. Open Source Contributions . . . . . . . . . . . . . . . . . . .17 1.2.3. Additional Contributions . . . . . . . . . . . . . . . . . . . 18 1.3. Structure of the Thesis . . . . . . . . . . . . . . . . . . . . .21 I. Model-Based Concept for Compression Schemes . . . . . . . . . . . 23 2. Compression-Aware In-Memory Query Processing . . . . . . . . . . .25 2.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.1. Vision of Compression-Aware In-Memory Query Processing . . . . 26 2.1.2. System Design Challenge for Compression-Aware Processing . . . 26 2.1.3. Our Contribution and Outline . . . . . . . . . . . . . . . . . 27 2.2. System Design Overview . . . . . . . . . . . . . . . . . . . . . 28 2.3. Survey of Lightweight Data Compression Algorithms . . . . . . . .29 2.3.1. Analysis of Basic Lightweight Compression Techniques . . . . . 29 2.3.2. Analysis of Lightweight Compression Algorithms . . . . . . . . 30 2.3.3. Derived System Description and Properties . . . . . . . . . . .31 2.4. COLLATE Model . . . . . . . . . . . . . . . . . . . . . . . . . .32 2.5. Transformation of Model Instances . . . . . . . . . . . . . . . .34 2.5.1. Model Instances for Byte-oriented Encoding Algorithms . . . . .34 2.5.2. Transformation to Executable Code . . . . . . . . . . . . . . .35 2.6. Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . .38 2.6.1. Structural Aspect . . . . . . . . . . . . . . . . . . . . . . .39 2.6.2. Operational Aspect . . . . . . . . . . . . . . . . . . . . . . 39 2.6.3. Optimization Aspect . . . . . . . . . . . . . . . . . . . . . .40 2.7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3. Metamodeling Lightweight Data Compression Algorithms . . . . . . .41 3.1. Problem Statement . . . . . . . . . . . . . . . . . . . . . . . .41 3.2. Metamodeling Lightweight Compression Algorithms . . . . . . . . .43 3.2.1. Properties of Data Compression Algorithms . . . . . . . . . . .43 3.2.2. COLLATE Metamodel . . . . . . . . . . . . . . . . . . . . . . .44 3.2.3. Interaction of COLLATE Concepts . . . . . . . . . . . . . . . .46 3.3. Application Scenarios . . . . . . . . . . . . . . . . . . . . . .46 3.3.1. Algorithms as Models . . . . . . . . . . . . . . . . . . . . . 46 3.3.2. Compression Algorithm Language CoALa . . . . . . . . . . . . . 48 3.3.3. Transformation of CoALa Code to Executable Code . . . . . . . .49 3.4. Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.5. Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 II. Model-Based Generator Framework . . . . . . . . . . . . . . . . .55 4. LCTL: Lightweight Compression Template Library . . . . . . . . . .57 4.1. Problem Statement . . . . . . . . . . . . . . . . . . . . . . . .57 4.2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . .59 4.2.1. Characteristics of Lightweight Compression . . . . . . . . . . 59 4.2.2. Metamodel COLLATE . . . . . . . . . . . . . . . . . . . . . . .60 4.3. Lightweight Compression Template Library . . . . . . . . . . . . 62 4.3.1. Template Metaprogramming for Tree Transformations . . . . . . .62 4.3.2. Lightweight Compression Template Library . . . . . . . . . . . 64 4.4. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.4.1. Format Space Diversity . . . . . . . . . . . . . . . . . . . . 71 4.4.2. Compile-Times . . . . . . . . . . . . . . . . . . . . . . . . .72 4.4.3. Run-Times . . . . . . . . . . . . . . . . . . . . . . . . . . .73 4.5. Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . .73 4.5.1. Further Code Optimization . . . . . . . . . . . . . . . . . . .74 4.5.2. Format Selection . . . . . . . . . . . . . . . . . . . . . . . 74 4.5.3. Integration . . . . . . . . . . . . . . . . . . . . . . . . . .75 4.6. Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5. Integrating Compression into Apache Arrow . . . . . . . . . . . . 77 5.1. Problem Statement . . . . . . . . . . . . . . . . . . . . . . . .77 5.2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . .79 5.2.1. Apache Arrow . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.2.2. Lightweight Integer Compression . . . . . . . . . . . . . . . .82 5.2.3. Lessons Learned . . . . . . . . . . . . . . . . . . . . . . . .83 5.3. ArrowComp Framework . . . . . . . . . . . . . . . . . . . . . . .83 5.3.1. Metamodel for (De)Compression . . . . . . . . . . . . . . . . .84 5.3.2. Self-Describing Columns . . . . . . . . . . . . . . . . . . . .85 5.3.3. Implementation . . . . . . . . . . . . . . . . . . . . . . . . 86 5.4. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.4.1. Data Sizes . . . . . . . . . . . . . . . . . . . . . . . . . . 90 5.4.2. Run Times . . . . . . . . . . . . . . . . . . . . . . . . . . .90 5.5. Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 92 5.5.1. Storage-oriented Formats . . . . . . . . . . . . . . . . . . . 92 5.5.2. Processing-oriented Formats . . . . . . . . . . . . . . . . . .93 5.5.3. Apache Arrow-centric Work . . . . . . . . . . . . . . . . . . .93 5.6. Conclusion and Future Work . . . . . . . . . . . . . . . . . . . 94 III. Generalized SIMD Concept for Integer Compression . . . . . . . .95 6. Partition-Based SIMD Processing . . . . . . . . . . . . . . . . . 97 6.1. Problem Statement . . . . . . . . . . . . . . . . . . . . . . . .97 6.2. Gather Evaluation . . . . . . . . . . . . . . . . . . . . . . . .99 6.2.1. Evaluation Setup . . . . . . . . . . . . . . . . . . . . . . . 99 6.2.2. Evaluation Results . . . . . . . . . . . . . . . . . . . . . .101 6.3. Partition-based SIMD . . . . . . . . . . . . . . . . . . . . . .105 6.4. Application Use Cases . . . . . . . . . . . . . . . . . . . . . 106 6.4.1. Vectorized Query Processing . . . . . . . . . . . . . . . . . 107 6.4.2. Integer Compression . . . . . . . . . . . . . . . . . . . . . 109 6.5. Related Work . . . . . . . . . . . . . . . . . . . . . . . . . .110 6.6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . .111 7. BOUNCE: Memory-Efficient SIMD Compression . . . . . . . . . . . .113 7.1. Problem Statement . . . . . . . . . . . . . . . . . . . . . . . 113 7.2. Analyzing State-of-the-Art . . . . . . . . . . . . . . . . . . .115 7.2.1. Bitpacking . . . . . . . . . . . . . . . . . . . . . . . . . .116 7.2.2. Simple Algorithms . . . . . . . . . . . . . . . . . . . . . . 120 7.2.3. Varint Algorithms . . . . . . . . . . . . . . . . . . . . . . 122 7.2.4. Further Compression Algorithms . . . . . . . . . . . . . . . .124 7.2.5. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 7.3. BOUNCE: Block concurrent SIMD Concept . . . . . . . . . . . . . 126 7.4. BOUNCE Application . . . . . . . . . . . . . . . . . . . . . . .128 7.4.1. Application to BP . . . . . . . . . . . . . . . . . . . . . . 128 7.4.2. Application to Simple Algorithms . . . . . . . . . . . . . . .130 7.4.3. Application to Varint Algorithms . . . . . . . . . . . . . . .130 7.4.4. Application to Further Algorithms . . . . . . . . . . . . . . 130 7.5. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . .131 7.5.1. Evaluation Setup . . . . . . . . . . . . . . . . . . . . . . .131 7.5.2. Performance of the Data Access Pattern . . . . . . . . . . . .132 7.5.3. Evaluating Bitpacking . . . . . . . . . . . . . . . . . . . . 132 7.5.4. Synthetic Data Sets with Fixed Bit Widths . . . . . . . . . . 133 7.5.5. Synthetic Data Sets with Different Bit Widths . . . . . . . . 134 7.5.6. Impact of Different Hardware Architectures . . . . . . . . . .135 7.5.7. Evaluation on Real Data Sets . . . . . . . . . . . . . . . . .136 7.6. Related Work . . . . . . . . . . . . . . . . . . . . . . . . . .137 7.7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . .137 8. Conclusion and Research Outlook . . . . . . . . . . . . . . . . .139 8.1. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 8.2. Research Outlook . . . . . . . . . . . . . . . . . . . . . . . .140

Dissertation (Dr. rer. nat.)--Institut für Informatik de Technischen Universität München, 2001. / Includes bibliographical references.