IAPG: Mitglieder

Thomas Brinkhoff: Dissertation

Der Spatial Join in Geo-Datenbanksystemen

Dissertation im Fach Informatik an der Fakultät für Mathematik der Ludwig-Maximilians-Universität München von Thomas Brinkhoff.

Tag der Einreichung: 1. September 1994
Tag der mündlichen Prüfung: 19. Dezember 1994

Berichterstatter:
Prof. Dr. Hans-Peter Kriegel, Ludwig-Maximilians-Universität München
Prof. Dr. Oliver Günther, Humboldt-Universität zu Berlin

Berichte aus der Informatik, Verlag Shaker, Aachen 1995, ISBN 3-8265-0529-8

Zusammenfassung

Die rechnergestützte Verwaltung, Darstellung und Auswertung geometrischer Daten hat in den letzten Jahren eine immer größere Bedeutung erlangt. Ein hauptsächliches Einsatzgebiet stellen dabei Geographische Informationssysteme dar. Wesentlicher Bestandteil solcher Systeme ist die Geo-Datenbank. Relationale Datenbanksysteme sind im Gegensatz zu betriebswirtschaftlich-administrativen Anwendungen, wo sie in einem großen Umfang eingesetzt werden, für die Verwaltung geometrischer Daten nur sehr beschränkt geeignet. Ein wesentliches Defizit ist dabei die geringe Effizienz bei der Bearbeitung raumbezogener geometrischer Anfragen und Operationen. Daher ist die Entwicklung von Geo-Datenbanksystemen erforderlich, die den Anforderungen von Geographischen Informationssystemen sowohl durch die zur Verfügung gestellten Datenmodelle und Anfragesprachen als auch durch eine adäquate physische Organisation der geometrischen Objekte Rechnung tragen.

Eine der wichtigsten Operationen in einem Geo-Datenbanksystem ist der Spatial Join. Der Spatial Join verknüpft diejenigen Objekte zweier Mengen von geometrischen Objekten miteinander, die ein geometrisches Prädikat erfüllen. Die wohl bedeutendste Variante des Spatial Joins - der Intersection Join - bestimmt alle Paare von Objekten, die sich schneiden. Im Rahmen der vorliegenden Arbeit wird ausgehend von der Annahme, daß nur räumlich nahe Objekte das Join- Prädikat erfüllen können, eine mehrstufige Bearbeitungsstrategie für den Spatial Join entworfen und exemplarisch anhand des Intersection Joins untersucht.

Die mehrstufige Join-Bearbeitung beruht im wesentlichen auf der folgenden Vorgehensweise: Zunächst wird auf Basis minimal umgebender Rechtecke mit Hilfe einer räumlichen Zugriffsstruktur - dem R*-Baum - eine Vorauswahl von Objektpaaren (Kandidaten) bestimmt, die das geometrische Join-Prädikat potentiell erfüllen. Für diesen sogenannten MBR-Join werden in der Arbeit verschiedene algorithmische Verfahren entwickelt und experimentell untersucht.

Ein darauffolgender geometrischer Filterschritt versucht auf Basis von Approximationen, möglichst viele Objektpaare als Antworten zu identifizieren oder aus der Kandidatenmenge auszuschließen. Für diesen Filterschritt werden eine Reihe von Verfahren getestet, die auf konservativen und progressiven Approximationen beruhen.

Für die verbliebenen Kandidatenpaare ist es daraufhin notwendig, deren vollständige geometrische Beschreibung vom Sekundärspeicher in den Hauptspeicher zu laden. Um den Aufwand für das Einlesen der Objekte zu verringern, wird eine Speicherungsorganisation zur räumlichen Clusterbildung vorgeschlagen und für den Spatial Join untersucht.

Im Verfeinerungsschritt wird schließlich für die eingelesenen Kandidatenpaare auf Grundlage der exakten Geometrie bestimmt, ob sie zur Antwortmenge gehören oder nicht. Durch eine Zerlegung der Objekte und eine geeignete Organisation der so erhaltenen Zerlegungskomponenten mittels einer räumlichen Datenstruktur kann gegenüber traditionellen Vorgehensweisen ein erheblicher Laufzeitgewinn erzielt werden.

Die verschiedenen Teilschritte werden zu einem geometrischen Join-Prozessor zusammengeführt und die Effektivität der einzelnen Schritte für unterschiedliche Ausgangssituationen untersucht. Anschließend wird dieser Prozessor in ein System zur geometrischen Anfragebearbeitung integriert, das einen Satz ausgewählter geometrischer Operationen für ein Geo-Datenbanksystem zur Verfügung stellt.

Die Arbeit schließt mit der Betrachtung des Spatial Joins für ein paralleles Rechnerarchitekturmodell auf Basis des Virtual Shared Memory. Ausgehend von einem einfachen Ansatz werden verschiedene Strategien entwickelt, um die Effizienz des parallelen Spatial Joins zu steigern. Auf einem konkreten Parallelrechner - der KSR1- wird experimentell demonstriert, daß durch die Parallelisierung des Spatial Joins ein linearer Speed up zu erzielen ist.

Inhaltsverzeichnis

  1. EINFÜHRUNG UND MOTIVATION
  2. GEOMETRISCHE ANFRAGEBEARBEITUNG
    1. Geo-Objekte und Karten
      1. Identität und Geometrie von Geo-Objekten
      2. Thematik von Geo-Objekten
      3. Karten
      4. Eigenschaften von Geo-Objekten und Karten
    2. Geometrische Selektionen
    3. Modell eines geometrischen Anfrageprozessors
      1. Räumliche Zugriffsstruktur
      2. Approximationsfilter
      3. Übertragung der exakten Geometrie
      4. Test der exakten Geometrie
    4. Spatial Join
      1. Allgemeiner Spatial Join
      2. Intersection Join
      3. MBR-Join
      4. Selektivität
      5. Zusammenfassung
  3. JOIN AUF BASIS DES R-BAUMS
    1. Anforderungskatalog an Verfahren für MBR-Joins
    2. Algorithmen zur Ausführung von Joins
      1. Nested-Loops Join
      2. Hash Join
      3. Sort-Merge Join
      4. Join-Indizes
    3. Zugriffsstrukturen und Joins
      1. Nicht-räumliche Zugriffsstrukturen und Joins
      2. Räumliche Zugriffsstrukturen und Joins
    4. R-Baum, R*-Baum und R-Join
      1. Datenstruktur des R-Baums
      2. Basisalgorithmen des R-Baums
      3. Algorithmen des R*-Baums
      4. R-Join
      5. Leistungsuntersuchung
    5. Optimierung der CPU-Kosten des R-Joins
      1. Einschränken des Suchraums
      2. Plane-Sweep Intersection Test
      3. Leistungsvergleich
    6. Optimierung der I/O-Kosten des R-Joins
      1. Plane-Sweep-Ordnung
      2. Plane-Sweep-Ordnung mit Pinnen
      3. Z-Ordnung (mit Pinnen)
      4. Hilbert-Ordnung (mit Pinnen)
      5. Leistungsvergleich
      6. R-Join zwischen Bäumen unterschiedlicher Höhe
    7. Optimierter R-Join
      1. Vergleich des naiven und optimierten R-Joins
      2. Prüfen des Anforderungskatalogs
    8. Zusammenfassung und Integration in den Join-Prozessor
  4. APPROXIMATIONSFILTER
    1. Approximationsfilter zur Bearbeitung geometrischer Selektionen
      1. Konvexe konservative Approximationen
      2. Güte der ausgewählten Approximationen
    2. Identifikation von Fehltreffern
    3. Identifikation von Treffern
      1. Kreuztest
      2. Fehlflächentest
      3. Progressive Approximationen
    4. Integration von Approximationen in die Zugriffsstruktur
      1. Formen der Integration
      2. Operationen auf den Approximationen
    5. Leistungsvergleich
    6. Zusammenfassung und Integration in den Join-Prozessor
  5. ÜBERTRAGUNG DER GEO-OBJEKTE
    1. Speicherung großer Mengen von Geo-Objekten
      1. Zugriff und Clusterbildung
      2. Organisationsmodelle
    2. Clusterorganisation
      1. Entwurf der Clusterorganisation
    3. Leistungsuntersuchung
      1. Aufbaukosten
      2. Speicherplatzausnutzung
      3. Window Queries
      4. Point Queries
    4. Leistungsuntersuchung des Spatial Joins
      1. Vergleich der verschiedenen Organisationsmodelle
      2. Anfragetechniken für die Clusterorganisation
      3. Auswirkungen der globalen Clusterbildung auf den Spatial Join
    5. Zusammenfassung und Integration in den Join-Prozessor
  6. TEST DER EXAKTEN GEOMETRIE
    1. Plane-Sweep-Ansatz
      1. Schnittsuche
      2. Polygon-in-Polygon-Test
    2. TR*-Baum-Ansatz
      1. Repräsentation der Polygone
      2. Der TR*-Baum
    3. Leistungsvergleich
      1. Gewichtung der Operationen
      2. Der Plane-Sweep-Ansatz
      3. TR*-Baum-Ansatz
      4. Auswirkungen auf das Laufzeitverhalten eines Spatial Joins
    4. Zusammenfassung und Integration in den Join-Prozessor
  7. DER GEOMETRISCHE JOIN-PROZESSOR
    1. Konzeption des geometrischen Join-Prozessors
    2. Zusammenspiel der Teilschritte
      1. Leistungsgewinn
      2. Kostengliederung
    3. Integration in GENESYS
    4. Zusammenfassung
  8. PARALLELER SPATIAL JOIN
    1. Virtual Shared Memory
    2. Paralleler Spatial Join
      1. Ein erster Ansatz
      2. Dynamische Aufgabenübernahme
      3. Pufferorganisation
      4. Aufgabenzuordnung
    3. Leistungsuntersuchung
      1. Untersuchung der dynamischen Aufgabenübernahme
      2. Untersuchung der Pufferorganisationen und Aufgabenzuordnung
      3. Untersuchung der Antwortzeit
    4. Zusammenfassung
  9. SCHLUSSBEMERKUNGEN
  10. LITERATURVERZEICHNIS
  11. SYMBOLVERZEICHNIS
  12. STICHWORTVERZEICHNIS
  13. LEBENS- UND BILDUNGSGANG

 

Impressum der Jade HochschuleDatenschutzerklärung der Jade Hochschule

Legal Notice of Jade UniversityProvacy Notice