The UB-Tree is an index structure for multidimensional point data. By name, it claims to be universal, but this imposes a huge burden, as there are few things which really prove to be universal. This thesis takes a closer look at aspects where the UB-Tree is not universal at a first glance. The first aspect is the discussion of space filling curves (SFCs), in particular comparing the Z-curve and the Hilbert-curve. The Z-curve is used to cluster data indexed by the UB-Tree and we highlight its advantages in comparison to other SFCs. While the Hilbert-curve provides better clustering, the Z-curve is superior w.r. to other metrics, i.e. it is significantly more efficient to calculate addresses and the mapping of queries to SFC-segments, and it is able to space efficiently index arbitrary universes. Thus the Z-curve is more universal here. The second aspect are bulk operations on UB-Trees. Especially for data warehousing the bulk insertion and deletion are crucial operations. We present efficient algorithms for incremental insertion and deletion. The third aspect is the comparison of the UB-Tree with bitmap indexes used for an example data warehousing application. We show how performance of bitmap indexes is increased by clustering the base table according to a SFC. Still the UB-Tree proves to be superior. The fourth aspect is the efficient management of data with skewed data distributions. The UB-Tree adapts its partitioning to the actual data distribution, but in comparison to the R-Tree, it suffers from being not able to prune search path leading to unpopulated space (= dead space). This is caused by partitioning the complete universe with separators. We present a novel index structure, the bounding UB-Tree (BUB-Tree), which is a variant of the UB-Tree inheriting its worst case guarantees for the basic operations while efficiently addressing queries on dead space. In comparison to R-Trees, its query performance is similar while offering superior maintenance performance and logarithmic worst case guarantees, thus being more universal than the R*-Tree. The last aspect addressed in this thesis is the management of spatial data. The UB-Tree is an index designed for point data, however also spatial objects can be indexed efficiently with it by mapping them to higher dimensional points. We discuss different mapping methods and their performance in comparison to the RI-Tree and R*-Tree. Our conclusion: The UB-Tree comes closer to being an universal index than any other competing index structure. It is flexible, dynamic, relatively easy to integrate into a DBMS kernel, and provides logarithmic worst case guarantees for the basic operations of insertion, deletion, and update. By extending its concepts to the BUB-Tree it is able to efficiently support skewed queries on skewed data distributions.     «

The UB-Tree is an index structure for multidimensional point data. By name, it claims to be universal, but this imposes a huge burden, as there are few things which really prove to be universal. This thesis takes a closer look at aspects where the UB-Tree is not universal at a first glance. The first aspect is the discussion of space filling curves (SFCs), in particular comparing the Z-curve and the Hilbert-curve. The Z-curve is used to cluster data indexed by the UB-Tree and we highlight its ad...     »

Um flexible Anfragen auf mehrdimensionale Daten effizient unterstützen zu können, ist eine optimierte Organisation der Daten nötig. Dabei müssen auch dynamische Daten und ungleichmäßige Datenverteilungen performant verwaltet werden. In dieser Arbeit wird daher neben der Anfragebearbeitung auch ein Schwerpunkt auf die flexible Verwaltung von mehrdimensionalen Daten mit dem UB-Baum gelegt. Dabei zeigt sich die Z-Kurve in Bezug auf Flexibilität und Effizienz als Gewinner gegenüber anderen bekannten raumfüllenden Kurven. Des Weiteren werden optimierte Algorithmen zum Laden und Löschen großer Mengen von Daten vorgestellt. Auch im Vergleich mit Bitmap-Indices am Beispiel eines Data Warehouse zeigt sich die Überlegenheit des UB-Baums. Für effiziente Bereichsanfragen auf leeren Räumen wurde die Variante "Bounding UB-Baum" entwickelt. Abschließend wurde die Indexierung ausgedehnter Objekte durch die Transformation der Objekt-Approximation und räumlicher Anfragen untersucht.     «

Um flexible Anfragen auf mehrdimensionale Daten effizient unterstützen zu können, ist eine optimierte Organisation der Daten nötig. Dabei müssen auch dynamische Daten und ungleichmäßige Datenverteilungen performant verwaltet werden. In dieser Arbeit wird daher neben der Anfragebearbeitung auch ein Schwerpunkt auf die flexible Verwaltung von mehrdimensionalen Daten mit dem UB-Baum gelegt. Dabei zeigt sich die Z-Kurve in Bezug auf Flexibilität und Effizienz als Gewinner gegenüber anderen bekannten...     »