Verpackung von R-Bäumen mit raumfüllenden Kurven

Die massive Menge an Daten und die große Vielfalt an Datenverteilungen im Zeitalter der großen Daten erfordern Zugriffsmethoden, die sowohl bei der Abfrageverarbeitung als auch beim Indexmanagement effizient sind und sowohl bei praktischen als auch bei Worst-Case-Workloads funktionieren. Um diesem Bedarf gerecht zu werden, betrachten wir zwei klassische multidimensionale Zugriffsmethoden – den R-Baum und die raumfüllende Kurve – neu. Wir schlagen eine neuartige R-Baum-Verpackungsstrategie basierend auf raumfüllenden Kurven vor. Diese Strategie erzeugt R-Bäume mit einer asymptotisch optimalen I/O-Komplexität für Fensterabfragen im Worst Case. Experimente zeigen, dass unsere R-Bäume bei der Abfrage sowohl von realen als auch von synthetischen Daten unterschiedlicher Verteilungen höchst effizient sind. Die vorgeschlagene Strategie ist auch einfach zu parallelisieren, da sie nur auf Sortierung beruht. Wir schlagen einen parallelen Algorithmus für das Bulk-Loading von R-Bäumen basierend auf der vorgeschlagenen Verpackungsstrategie vor und analysieren dessen Leistung unter dem massiv-parallelen Kommunikationsmodell. Um dynamische Datenaktualisierungen zu handhaben, schlagen wir zusätzlich Indexaktualisierungsalgorithmen vor, die Datenoperationen für Einfügungen und Löschungen verarbeiten, ohne die optimale Abfrage-I/O-Komplexität zu beeinträchtigen. Die experimentellen Ergebnisse bestätigen die Wirksamkeit und Effizienz der vorgeschlagenen Bulk-Loading- und Aktualisierungsalgorithmen für R-Bäume über große Datensätze.