Post on 06-Apr-2016
transcript
- Überblick -
Motivation
GIS G - IS
Geo Informationssystem
• erdbezogen
• raumbezogen
System zum ‚Handling‘ von Informationen = Daten
System zum Umgang mit erd-/ raumbezogenen Daten
MotivationInformationssystem
Erfassung Speicherung Verarbeitung Aktualisierung Visualisierung
• Einfügen
• Ändern
• Löschen
• dauerhaft
• platzsparend
• strukturiert
• für primären und sekundären Speicher
• range queries
• nearest neighbourhood queries
• statistische Analysen
Basis: raumbezogene / erdbezogene Daten
Motivation
raumbezogene / erdbezogene Daten:
• unregelmäßig
• umfangreich
• dynamisch
Beispiel Höhendaten:
• unregelmäßig und
• umfangreich
Beispiel Grenzverhältnisse
• dynamisch und
• umfangreich
Anmerkung:
Die Eigenschaften hängen natürlich von dem Maßstab ab, in dem sie betrachtet werden...
MotivationBeispiel
Verknüpfung der Telefonnummern aller Einwohner einer Stadt mit den Standorten der Anschlüsse...
„Suche in einem Stadtviertel alle Telefonnummern beginnend mit 5 und endend mit 3.“
Müller 5123122 Meier 4564123 Becker 54112 Schäfer 378122 ...
Dauert mit einem Telefonbuch und einem Stadtplan mehrere Tage...
MotivationFolgerungen
Für das Handling von Geo-Daten mit den Zielsetzungen eines GIS sind Verfahren notwendig, die
1. den Zugriff auf die Daten und generell die Speicherung der Daten in den verschiedenen Speichern erlauben, und
2. diese Aufgaben schnell und effizient ausführen, um die Interaktivität zu gewährleisten.
Respektive...
Es gilt auch eine Lösung für die effiziente Speicherung von mehrdimensionalen Daten im eindimensionalen Speicher zu finden, da dies immensen Einfluss auf die Funktionalität eines GIS hat...
Raumbezogene Zugriffsverfahren
Zielsetzungen
Unterstützung schnellen Zugriffs auf raumbezogene Daten, sowie effiziente Speicherung dieser für z.B. ...
• range queries
„Finde alle gespeicherten Objekte, die in den definierten Suchbereich passen“
• nearest neighbourhood queries
„Finde die Objekte mit der minimalen Entfernung zu dem gegebenen Punkt“
• raumbezogene Analysen/ Operationen
z.B. map overlay + =
Raumbezogene ZugriffsverfahrenAus diesen Überlegungen resultieren einige
Notwendige Eigenschaften
„Spatial Indexing“
• Strukturierung der Daten mittels bestimmter Kriterien
• Vermeidung des Zugriffs auf jedes einzelne Element der immensen Datenmengen bei den verschiedenen Datenbankanfragen (queries), um die geforderte Interaktivität zu gewährleisten.
sonst...
Zzzzz..Zzzzz..Zzzz...
Raumbezogene Zugriffsverfahren
Notwendige Eigenschaften„Clustering“
• Aufteilung der Daten gemäß ihrer Nutzungshäufigkeit und/oder Nachbarschaftsverhältnisse Lage der Daten im Speicher ähnelt der ‚Lage‘ in der Realität
• Vermeidung der unkontrollierten und unsortierten, „wilden“ Speicherung, da die Daten aufgrund des Umfanges auch im langsamen Sekundärspeicher gespeichert werden müssen
Veranschaulichung: 10.000.000 Zugriffe...
Dauer: 0,01 s Dauer: 10 s
Raumbezogene Zugriffsverfahren
Platz und Zeit sind knappe Güter
Exkurs / Wiederholung: BäumeAuffrischung des Inhalts von Diskrete Mathematik II...
Freier BaumGraph ohne Zyklen mit nur einer Komponente
BinärbaumBaum, dessen Knoten maximal 2 Nachfolger
haben
ausgeglichen, falls sich in jedem Knoten die Anzahl der Knoten im linken und rechten Teilbaum um höchstens 1 unterscheiden
Baum - TreeFreier Baum, von dem ein Knoten als Wurzel
ausgezeichnet ist
Exkurs / Wiederholung: Bäume
Suchbaum – Trie (von engl. reTRIEval)
Jeder Knoten wird mit einem Schlüssel belegt, in der Weise, daß der linke Nachfolger und dessen Nachfolgeknoten kleinere Schlüssel, und der rechte Nachfolgeknoten mit allen Nachfolgeknoten größere Schlüssel haben.
9
4
2 7
17
13 23
WurzelInnerer Knoten
äußerer Knoten/ Blatt
Zugriffsverfahren
kd – Tree• Speicherung von k-dimensionalen Punktobjekten (hier beispielhaft zwei
Dimensionen)
• Die gesamte Region wird durch die Wurzel referenziert
• Jeder innere Knoten enthält einen Punkt und referenziert eine rechteckige Region, die wiederrum in zwei rechteckige Regionen unterteilt wird. Auf geraden Höhen des Baumes geschieht dies durch die y-Koordinate; auf Ungeraden durch die x-Koordinate
Zugriffsverfahren
kd – Tree
• Jeder neue Punkt führt zu einem neuen inneren Knoten
• Operation ‚Einfügen‘ sehr simpel, dafür führen ‚Löschen‘ und ‚Ändern‘ zu großen Problemen
• Die Struktur des Baumes ist in hohem Maße von der Reihenfolge des Einfügens der Punkte abhängig
• Baum ist unausgeglichen... im ‚worst case‘: pro Punkt eine neue Ebene!
Zugriffsverfahren
adaptive kd – Tree
• Wahl der Punkte, die ein Gebiet referenzieren, nicht mehr auf gegebene Punktmenge beschränkt
• Erzeugung von gleiche Punktmengen enthaltender Regionen Baum ist ausgeglichen
• Neues Problem: dynamisches Handling und gleichzeitige Ausgleichung des Baumes sehr schwierig
• Leistungsfähigkeit (bei 2 Dimensionen)
• build time: O( n log(n) )
• range query: O( sqrt(n) + Anzahl gefundener Punkte)
Zugriffsverfahren
kdB – Tree • Kombination aus kD – Tree und B – Tree
• Ziele...
• Effizienz für Ein-/Ausgabe bestimmt durch B – Tree
• Effizienz für mehrdimensionale Suchanfragen bestimmt duch kD – Tree
• Interne Knoten enthalten mehr als ein Datenobjekt; der maximale Wert wird durch die ‚bucket-size‘ bestimmt
• ‚bucket-size‘ – Größenangabe, die angibt, wie viele Datenobjekte maximal in eine ‚page‘ (=Seite) des Speichers passen Minimierung der Anzahl der Speicherzugriffe, sowie Geschwindigkeitsvorteil
• Ständige Ausbalancierung des Baumes
• Problem: ungeeignet für räumlich ausgedehnte Objekte GIS
Zugriffsverfahren
BSP – Tree (Binary Space Partitioning Tree)
• Nutzung von Liniensegmenten von Polylinien und deren Ecken zur rekursiven Unterteilung des Raumes (nicht rechteckig)
A
B
DC
A
D1B
D1
C
links rechts
D2D2
• Gut geeignet für raumbezogene Operationen, jedoch nur für beziehungslose Liniensegmente für GIS noch Erweiterung nötig...
Zugriffsverfahren
multi object BSP – Tree
• Erweiterung der BSP – Tree struktur Speicherung der zu einem Objekt gehörigen Liniensegmenten mit explizieter Referenzierung in den Blättern
R
D
R
R D
• Problem: Objekte sind über mehrere Äste verteilt
• Vorteil: effiziente raumbezogene Operationen möglich
ZugriffsverfahrenPoint Quadtree
• Unterteilung des Datenraums (Punktraums) in Quadranten mit den vorhandenen Punkten als Zentrum
• Jeder Knoten hat vier Nachfolger (NW,NO,SW,SO) und enthält selber die Punktkoordinaten des Zentrums, sowie evtl. weitere Informationen
NWNO SW
SO
Zugriffsverfahren
Point Quadtree
• Baumstruktur ist von der Reihenfolge des Einfügens der Punkte abhängig … nicht eindeutig
• Entstehung von unausgeglichenen Bäumen – ‘worst case’ … nur ein Ast
• Operation Einfügen ist trivial; Operationen Ändern und Löschen können jedoch die Struktur des Baumes radikal verändern ungeeignet für dynamische Daten, jedoch geeignet z.B. für die Speicherung von Rasterdaten
• Leistungsfähigkeit:
• build time: O( n log(n) )
• point query: O( log(n) )
Zugriffsverfahren
Region Quadtree
• Speicherung einer Rasterapproximation eines Polygons
Rekursive Unterteilung des relevanten Bereichs in Quadrate, bis jedes einzelne Quadrat entweder komplett innerhalb oder ausserhalb liegt, oder die maxiamle Auflösung erreicht wurde
• Problem: nur näherungsweise / Approximation
• Prinzip für das Speichern von Rasterinformationen geeignet...
Zugriffsverfahren
Fixed Grid
• Unterteilung des Raumes in gleich große Zellen (regelmäßiges Raster)
• Alle Punkte, die in einer Zelle liegen, werden gemeinsam im Speicher abgelegt gute Performance für range queries
• großer Nachteil: es wird auch Speicherplatz für leere Zellen verbraucht
• Ferner: Das fixed Grid ist unsensibel gegenüber unregelmäßigen Datenverteilungen
Zugriffsverfahren
Grid File
• Erweiterung des fixed grid
• Basisidee: Zuordnung der Datenblöcke zu den physikalischen Speichereinheiten (buckets) des Speichermediums
• Durch Einführung des ‚grid-directory‘ wird die Unterteilung abhängig von der Punktverteilung realisiert
• v.a. geeignet für dynamische Daten, da Einfügen und Löschen, sowie Verändern sehr einfach sind...
x
y
Grid directory
C BBA
Zugriffsverfahren
R - Tree
• Gruppierung der Objekte in einer hierarchischen Struktur auf Grundlage ihrer Lage
• Verwendung der sog. ‚bounding boxes‘ zur Gruppierung – minimale umschließende Rechtecke (MBR‘s)
• Inhalt der Blätter: Zeiger auf die kompletten Objekte, sowie Angabe des MBR‘s
• Inhalt der internen Knoten: Zeiger auf den Nachfolger und Angabe dessen MBR‘s
• ‚branching factor‘: maximale Anzahl der Einträge pro Knoten; abhängig von der ‚page size‘ ... Performancesteigerung
• Vorteil: Objekte werden komplett referenziert und nicht auseinandergenommen
Zugriffsverfahren
R - Tree
C
A BE
D
GF
H
K J
I A B C
D E F G H I J K
branching factor 4
Zusammenfassung
Verfahren Vorteile Nachteile Geeignet für
kd - Tree Einfache StrukturNicht eindeutig,Unausgeglichen
Statische Punktmenge
adaptive kd - Tree Schnelle Suche Komplexe Strukturmäßig
dynamische Punktmengen
kdB - Tree Speicherorientiert, schnell, dynamisch
Nicht für räumliche Objekte geeignet
Dynamische Punktmengen
Datentauglichkeit:
Rasterdaten
Punktdaten
Objektdaten
Zusammenfassung
Verfahren Vorteile Nachteile Geeignet für
BSP – TreeGutes Handling raumbezogener
Operationen
Nur für beziehungslose Liniensegmente
Beziehungslose Raumdaten
Multi object BSP Tree
Effiziente raumbezogene
Operationen
Objekte verteilen sich über mehrere Äste - Komplexität
GIS
Datentauglichkeit:
Rasterdaten
Punktdaten
Objektdaten
Zusammenfassung
Verfahren Vorteile Nachteile Geeignet für
Point Quadtree Einfache StrukturNicht eindeutig, unausgeglichen, nicht dynamisch
Statische Rasterdaten
Region Quadtree
Einfache Approximation von
‚ausgedehnten‘ Objekten
nur näherungsweise
Beschreibung
statischeRasterdaten
Fixed GridEinfache Struktur,
intelligente Speichernutzung
speicherintensivgleichmäßig
verteilte Punktdaten
Grid File
Dynamisches Datenhandling sehr einfach, einfache
Struktur, intelligente Speichernutzung
primär für Punktdaten vorgesehen
dynamische, mehr-
dimensionale Punktdaten
Rasterdaten Punktdaten Objektdaten
Zusammenfassung
Verfahren Vorteile Nachteile Geeignet für
R – Tree
komplette Objektreferenzierung
Intelligente Speichernutzung
Ausgeglichenheit abhängig von
EinfügereihenfolgeGIS
Rasterdaten Punktdaten Objektdaten