Efficient indexing and view dependent ranking in CFD databases [Elektronische Ressource] / vorgelegt von Christoph Brochhaus

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2008
• Nombre de lectures: 18
• Langue: Deutsch
• Poids de l'ouvrage: 14 Mo

Extrait

Efficient indexing and view-dependent
ranking in CFD databases
Von der Fakultät für Mathematik, Informatik und
Naturwissenschaften der RWTH Aachen University zur Erlangung
des akademischen Grades eines Doktors der Naturwissenschaften
genehmigte Dissertation
vorgelegt von
Diplom-Informatiker Christoph Brochhaus
aus Düren
Berichter: Universitätsprofessor Dr. rer. nat. Thomas Seidl
Univ Christian Bischof, Ph.D.
Tag der mündlichen Prüfung: 24. Juni 2008
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfügbar.Contents
Acknowledgements 1
Abstract 2
Zusammenfassung 4
List of Figures 7
I Preliminaries 11
1 Introduction 12
1.1 Computational fluid dynamics (CFD) . . . . . . . . . . . . . . . . 12
1.2 Interactive CFD post-processing and virtual reality (VR) . . . . . 13
1.3 Data management and querying of large CFD data sets . . . . . . 15
1.4 IndeGS - Index supported graphics data server . . . . . . . . . . . 17
1.5 Efficient interval querying in RDBMS . . . . . . . . . . . . . . . . 17
1.6t Voronoi-assisted nearest-neighbor querying . . . . . . . . 18
1.7 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
II CFD Data Indexing 21
2 IndeGS - Index supported graphics data server 22
2.1 Motivation and benefits . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 System architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Query interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4 Demonstration setup . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 Indexing CFD Data 29
3.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Index support for view-oriented CFD post-processing . . . . . . . 33
3.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
III Query Processing on CFD Data Indexes 43
iii4 View-dependency 44
4.1 Introduction to query processing . . . . . . . . . . . . . . . . . . . 44
4.2 View-dependent distance functions . . . . . . . . . . . . . . . . . 47
4.3 MINDIST calculation . . . . . . . . . . . . . . . . . . . . . . . . . 57
5 Queries with Static User 59
5.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2 Query processing . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.3 Priority queue handling . . . . . . . . . . . . . . . . . . . . . . . . 61
5.4 MINDIST approximations . . . . . . . . . . . . . . . . . . . . . . 63
5.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6 Queries with Dynamic User 71
6.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.2 Queue rearrangement . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.3 Update frequency . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
7 Time-dependent queries 80
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
7.2 Prefetching strategies . . . . . . . . . . . . . . . . . . . . . . . . . 81
7.3 Queue handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.4 Integration in IndeGS . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
IV Indexing of CFD Data with RDBMS 99
8 The relational interval tree (RI-tree) 100
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
8.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
8.3 DB2 Extensible Indexing Framework . . . . . . . . . . . . . . . . 106
8.4 Relational mapping of the interval tree structure . . . . . . . . . . 109
8.5 Adaptation of query processing . . . . . . . . . . . . . . . . . . . 116
8.6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
8.7 RI-tree conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . 133
9 Integration of the RI-tree in IndeGS 134
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
9.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
9.3 System architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 137
9.4 Index generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
9.5 Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
iv9.6 Handling of metadata . . . . . . . . . . . . . . . . . . . . . . . . . 146
RI10 Ranking Queries in IndeGS 149
10.1 Approximate Geometric Ranking . . . . . . . . . . . . . . . . . . 149
10.2 Query processing . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
10.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
10.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
V Voronoi-Based Nearest Neighbor Search 163
11 Voronoi cells and dimensionality reduction 164
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
11.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
11.3 Bounding constraints complexity . . . . . . . . . . . . . . . . . . 173
11.4 Reduction of bounding constraints complexity . . . . . . . . . . . 175
12 Dimensionality reduction and indexing 179
12.1 Bounding cuboid dimensionality reduction . . . . . . . . . . . . . 179
12.2 Main memory indexing . . . . . . . . . . . . . . . . . . . . . . . . 182
12.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
12.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
VI Conclusion 191
13 Summary 192
14 Future work 194
A CFD data sets 197
A.1 Engine data set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
A.2 Delta wing data set . . . . . . . . . . . . . . . . . . . . . . . . . . 198
A.3 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
Bibliography 200
vAcknowledgements
First of all, I would like to express my deepest gratitude to the supervisor of
this thesis, Prof. Dr. Thomas Seidl. Thank you for giving me the opportunity
to pursue my Ph.D. thesis and letting me take part in the early stages of the
establishment of your Data Management and Exploration Group. I am much
obligedtoyouforyourhelpfulsupportandformanyhoursofprofitablediscussions
about my research.
Furthermore, I am very grateful to Prof. Christian Bischof, Ph.D. from the Cen-
ter for Computing and Communication, RWTH Aachen University, for agreeing
to act as a co-referee for this thesis. Thank you for your interest in my research.
Additional thanks belong to Andreas Gerndt from the same institute for ap-
proaching our research group with the challenge to create out-of-core strategies
for post-processing CFD data. My thanks also go out to Marc Wolter for contin-
uing the collaboration and integrating the server IndeGS into their virtual reality
setup.
Special thanks go to all my colleagues and students (former and current) at the
Chair of Computer Science 9, too numerous to mention them all, for the friendly
and pleasant atmosphere as well as many fruitful discussions over the last years.
1Abstract
Methods numerically simulating the interaction of gases or fluids with complex
surfaces (computational fluid dynamics, CFD) are able to perform calculations
with increasing levels of detail due to the ongoing development of more powerful
computers. CFD simulations are utilized during the design of e.g. combustion
engines or airplanes, amongst many others. An increasing level of detail on the
one hand allows for more accurate and meaningful simulation results proving very
useful in industrial development and research. On the other hand, huge amounts
of raw CFD data are generated and need to be repeatedly accessed during the
subsequent interactive post-processing (e.g. isosurface extraction) by experts in
the application domain. The efficiency of post-processing can be significantly
increased by the use of virtual reality (VR) technology, letting users immerse into
the visualized data sets and extracted features.
Interactive post-processing is efficiently performed on data sets stored in main
memory, which outperforms secondary storage by magnitudes regarding access
times. Large CFD data sets not fitting into main memory thus require efficient
secondary storage methods.
In this thesis, methods are introduced which appropriately arrange CFD data
on secondary storage and allow for an efficient access during post-processing. The
efficiency of post-processing is improved by novel view-dependent query methods.
The continuous extraction and visualization of partial results in the proximity
and direct line of sight of the user allow for a “quick first impression” of the result
set. The approaches are enhanced by dynamic aspects, reacting to a user freely
roaming the VR environment with immediate alignment of query execution and
2of the result data stream. For CFD data sets simulated over a span of time,
prefetching methods allowing for a dynamic visualization of different time steps
are presented.
Furthermore, the index supported graphics data server IndeGS is presented,
which offers the developed indexing and access