title: Efficient bulk-loading methods for temporal and multidimensional index structures
title: Effiziente Bulk-loading-Verfahren für temporale und multidimensionale Indexstrukturen
Creators: name: Achakeev, Daniar
Publisher: name: Philipps-Universität Marburg
Year: 2014
Subjects: Informatik
Datenbanksystem
Index structure
Datenstruktur
Algorithmus
MVBT
R-tree
Bulk-loading

description: Nahezu alle naturwissenschaftlichen
      Bereiche profitieren von neuesten Analyse- und
      Verarbeitungsmethoden für große Datenmengen. Diese Verfahren
      setzten eine effiziente Verarbeitung von geo- und
      zeitbezogenen Daten voraus, da die Zeit und die Position
      wichtige Attribute vieler Daten sind. Die effiziente
      Anfrageverarbeitung wird insbesondere durch den Einsatz von
      Indexstrukturen ermöglicht. Im Fokus dieser Arbeit liegen
      zwei Indexstrukturen: Multiversion B-Baum (MVBT) und R-Baum.
      Die erste Struktur wird für die Verwaltung von zeitbehafteten
      Daten, die zweite für die Indexierung von mehrdimensionalen
      Rechteckdaten eingesetzt. Ständig- und schnellwachsendes
      Datenvolumen stellt eine große Herausforderung an die
      Informatik dar. Der Aufbau und das Aktualisieren von Indexen
      mit herkömmlichen Methoden (Datensatz für Datensatz) ist
      nicht mehr effizient. Um zeitnahe und kosteneffiziente
      Datenverarbeitung zu ermöglichen, werden Verfahren zum
      schnellen Laden von Indexstrukturen dringend benötigt. Im
      ersten Teil der Arbeit widmen wir uns der Frage, ob es ein
      Verfahren für das Laden von MVBT existiert, das die gleiche
      I/O-Komplexität wie das externe Sortieren besitz. Bis jetzt
      blieb diese Frage unbeantwortet. In dieser Arbeit haben wir
      eine neue Kostruktionsmethode entwickelt und haben gezeigt,
      dass diese gleiche Zeitkomplexität wie das externe Sortieren
      besitzt. Dabei haben wir zwei algorithmische Techniken
      eingesetzt: Gewichts-Balancierung und Puffer-Bäume. Unsere
      Experimenten zeigen, dass das Resultat nicht nur
      theoretischer Bedeutung ist. Im zweiten Teil der Arbeit
      beschäftigen wir uns mit der Frage, ob und wie statistische
      Informationen über Geo-Anfragen ausgenutzt werden können, um
      die Anfrageperformanz von R-Bäumen zu verbessern. Unsere neue
      Methode verwendet Informationen wie Seitenverhältnis und
      Seitenlängen eines repräsentativen Anfragerechtecks, um einen
      guten R-Baum bezüglich eines häufig eingesetzten
      Kostenmodells aufzubauen. Falls diese Informationen nicht
      verfügbar sind, optimieren wir R-Bäume bezüglich der Summe
      der Volumina von minimal umgebenden Rechtecken der
      Blattknoten. Da das Problem des Aufbaus von optimalen
      R-Bäumen bezüglich dieses Kostenmaßes NP-hart ist, führen wir
      zunächst das Problem auf ein eindimensionales
      Partitionierungsproblem zurück, indem wir die Daten bezüglich
      optimierte raumfüllende Kurven sortieren. Dann lösen wir
      dieses Problem durch Einsatz vom dynamischen Programmieren.
      Die I/O-Komplexität des Verfahrens ist gleich der von
      externem Sortieren, da die I/O-Laufzeit der Methode durch die
      Laufzeit des Sortierens dominiert wird. Im letzten Teil der
      Arbeit haben wir die entwickelten Partitionierungsvefahren
      für den Aufbau von Geo-Histogrammen eingesetzt, da diese
      ähnlich zu R-Bäumen eine disjunkte Partitionierung des Raums
      erzeugen. Ergebnisse von intensiven Experimenten zeigen, dass
      sich unter Verwendung von neuen Partitionierungstechniken
      sowohl R-Bäume mit besserer Anfrageperformanz als auch
      Geo-Histogrammen mit besserer Schätzqualität im Vergleich zu
      Konkurrenzverfahren generieren lassen.
description: The recent increase of spatial and
      temporal data requires efficient algorithms for index
      construction and for bulk updates. Many big data applications
      exhibit not only a high volume of static data but also
      inherit data growth. Moreover, some of them display high
      update rates. Incoming collected or produced data arrive in
      batches in order to reduce transportation and update costs.
      Therefore, updating an index using one record at a time is
      found to be inefficient for sufficiently large batch sizes.
      In this work, we investigate the problem of efficient
      bulk-loading of temporal and spatial index structures. We
      design novel loading strategies for multiversion B-tree
      (MVBT) and R-tree. We introduce a novel loading algorithm for
      MVBT with the asymptotic optimal I/O complexity. We show that
      the previously developed technique based on the buffer tree
      solves the loading problem only for the special case (if an
      input file consists only of insert operations). In this work,
      we propose the first loading algorithm for MVBT that meets
      the lower-bound of external sorting. We also proposed an
      efficient algorithm for bulk updates. These results are
      achieved by a combination of two algorithmic techniques:
      buffer tree and weight balancing. In this work, we designed a
      loading algorithm for the R-tree that optimizes it according
      to a widely used cost model. Extensive experimental results
      show that R-trees built using our novel approach exhibit
      substantially better query performance than sort-based
      counterparts. The novelty of our technique is that if a query
      profile is available the algorithm is able to build better
      R-trees. We proposed the following heuristic: first, we
      define the best sorting order using the average shape of the
      query rectangle. Second, we reduce the bulk-loading problem
      to a one-dimensional partitioning problem by sorting the
      input set. Third, we find an optimal solution for this
      problem according to the proposed cost models. The motivation
      of our heuristic is NP-hardness of the optimization problem.
      Based on the result obtained from query adaptive loading, we
      observed that construction of spatial histograms resembles
      the problem of optimal loading of R-trees. Therefore, we
      developed a spatial histogram construction method based on
      the partitioning framework developed for R-tree loading.
      Spatial histograms built using our novel method exhibit high
      accuracy for different data and query distributions. Our
      method has only one parameter, minimal page capacity.
      Moreover, our extensive experimental results show robustness
      of our method for different query and data
      distributions.