Da in der computergestu¨tzten Geographie mit zum Teil sehr großen Mengen von ra¨umlichen Daten gearbeitet werden muss, hat sich mittlerweile die U¨ berzeugung durchgesetzt, solche Datensa¨tze in ra¨umlichen Datenbanken zu speichern. Allerdings wird bei der Entwicklung von geographischen Programmen dem Aspekt der Skalierbarkeit oftmals wenig Beachtung geschenkt. So enthalten verbreitete Programme fu¨r Geoinformationssysteme wenig bis keine sogenannten externen Algorithmen, die den Geschwindigkeitsunterschied zwischen internem (RAM) und externem Speicher (Festplatte) beru¨cksichtigen und versuchen, die Anzahl der I/O-Zugriffe auf letzteren zu minimieren. Diese Programme arbeiten daher nur dann effizient, wenn genug interner Speicher fu¨r die zu bearbeitenden Geodaten zur Verfu¨gung steht. Wir stellen in diesem Beitrag einen auf Partitionierung basierenden Ansatz vor, der den Aufwand fu¨r die Entwicklung von auf großen Geodatenmengen skalierenden Programmen stark reduziert. Dazu werden Zugriffe auf externe Speicher in eine vorgelagerte Partitionierungs- und eine nachgelagerte Rekompositionsphase verschoben und fu¨r diese Phasen flexible Operationen, die ein breites Spektrum an geographischen Problemstellungen unterstu¨tzen, als Partitionierungsdienst fu¨r ra¨umliche Datenbanksysteme angeboten.
Geoprogramme, die diese Prozesse implementieren, mu¨ssen aufgrund des betra¨chtlichen Umfangs von Geobasisdatensa¨tzen in der Lage sein, den begrenzten Hauptspeicher eines Rechners effizient zu verwalten, um Performanceprobleme aufgrund von Swapping oder Programmabstu¨rze wegen Speichermangels zu vermeiden. Dazu wu¨rde es sich anbieten, diese Programme als Datenbankanwendungen zu implementieren, die sa¨mtliche Datenzugriffe u¨ber SQL-Befehle abwickeln. Dieses Vorgehen ist jedoch mit einigen Nachteilen verbunden. Zuna¨chst ist man auf die von dem ra¨umlichen Datenbanksystem angebotene Funktionalita¨t fu¨r geometrische und geographische Berechnungen beschra¨nkt. Die freie Auswahl aus spezialisierten und optimierten SoftwareBibliotheken entfa¨llt. Weiterhin ha¨ngt die Performance von SQL-basierten Anwendungen entscheidend von der Qualita¨t der Anfrageoptimierung ab. Aufgrund der inha¨renten Schwierigkeit der Kostenscha¨tzung fu¨r geometrische Operationen stellt dies insbesondere bei ra¨umlichen Datenbanken ein Problem dar. Schließlich mu¨ssten die Algorithmen fu¨r Geoprogramme in eine relationale Formulierung umgewandelt werden, was aufgrund von deren Komplexita¨t i.A. aufwa¨ndig und fehleranfa¨llig ist. Hinzu kommt noch, dass die Entwickler geographischer Anwendungen oftmals keine Datenbankspezialisten sind.
Wir stellen in diesem Beitrag einen Ansatz vor, der diese Probleme durch Partitionierung der Geobasisdaten umgeht. Statt ein Geoprogramm auf den gesamten Datensatz anzuwenden, wird jede Datenpartition fu¨r sich allein bearbeitet, wobei diese so klein gewa¨hlt wird, dass der verfu¨gbare Hauptspeicher nicht u¨berfu¨llt wird. Die fu¨r die einzelnen Partitionen berechneten Ergebnisdatensa¨tze mu¨ssen anschließend wieder zu einem Gesamtdatensatz zusammengesetzt werden, was wir als Rekomposition bezeichnen. Da unterschiedliche Prozesse auch unterschiedliche Strategien fu¨r die Partitionierung und Rekomposition erfordern, bieten wir eine Sammlung solcher Operationen als Dienst auf einem ra¨umlichen Datenbanksystem an. Die Entwickler von Geoprogrammen ko¨nnen diesen u¨ber eine einfache Schnittstelle ansprechen, wodurch die Notwendigkeit entfa¨llt, innerhalb der Programme selbst den Austausch der Daten zwischen Haupt- und sekunda¨rem Speicher zu beru¨cksichtigen.
Fu¨r geographische Daten bietet es sich an, zur
Partitionierung die ra¨umliche Lage zu verwenden und
Datenobjekte aus einem zusammenha¨ngenden Gebiet in eine Partition
einzuteilen. Dieser Ansatz ist allgemein fu¨r Geoprogramme
anwendbar, die sich lokal verhalten. Dies bedeutet, dass fu¨r
die Berechnung von Ergebnissen an einer Position nur
Daten aus einer begrenzten Umgebung beno¨tigt werden und
diese Umgebung klein gegenu¨ber einer Partition ist. In
diesem Fall lassen sich Fehler, die insbesondere am Rand einer
Partition entstehen, weil dem Geoprogramm nicht alle
Daten zur Verfu¨gung stehen, reduzieren oder ganz vermeiden,
indem man sich u¨berlappende Partitionen erzeugt [
Der Rest des Beitrags ist wie folgt strukturiert: In Abschnitt 2 nennen wir Arbeiten, die mit unserem Ansatz verwandt sind. Abschnitt 3 beschreibt die Architektur und das Funktionsprinzip des Partitionierungsdienstes. In Abschnitt 4 verwenden wir die Liniensegmentierung als konkretes Anwendungsbeispiel und geben fu¨r diesen Prozess alternative Partitionierungs- und Rekompositionsoperationen an. Abschnitt 5 beschreibt die Ergebnisse von Experimenten mit diesen Operationen auf realen geographischen Daten. Schließlich liefert Abschnitt 6 ein Fazit u¨ber den in diesem Beitrag vorgestellten Ansatz und einen Ausblick auf Folgearbeiten.
Das Prinzip, Datensa¨tze zuerst aufzuteilen,
Teilergebnisse zu berechnen und spa¨ter aus den Teilergebnissen ein
Gesamtergebnis zu generieren, ist in der Informatik unter dem
Namen Divide-and-Conquer bekannt. Auch fu¨r geometrische
Probleme gibt es eine Reihe von Vorschla¨gen, beispielsweise
von Gu¨ting und Schilling [
Aufgrund seiner Wichtigkeit bei der Berechnung
ra¨umlicher Verbunde ist das Problem der Bestimmung von sich
u¨berschneidenden achsenparallelen Rechtecken besonders
intensiv untersucht worden. Wa¨hrend fu¨r interne Algorithmen
das Plane-Sweep-Paradigma [
Wir implementieren Partitionierungs- und Rekompositionsoperationen als Stored Procedures auf einem ra¨umlichen Datenbanksystem. Diese ko¨nnen u¨ber eine Datenbankschnittstelle von einem Steuerprogramm außerhalb der Datenbank aufgerufen werden, um in der Datenbank gespeicherte Daten fu¨r ein Geoprogramm aufzuteilen und wieder zusammenzusetzen (Abbildung 1). Das Steuerprogramm liest jeweils Abb. 1: Geoprogramm (Ablauf ) mit Partitionierung einen Eintrag aus dem Partitionierungsschema (Abschnitt 3.2), das die Geometrien der Partitionen entha¨lt. Damit wird eine geeignete Partitionierungsoperation aufgerufen und eine Partition der Ausgangsdaten berechnet. Diese muss in ein von dem Geoprogramm verwendetes Dateiformat exportiert werden, bevor dieses vom Steuerprogramm aufgerufen wird, um fu¨r die Datenpartition ein Ergebnis zu berechnen, das zuna¨chst ebenfalls im Dateisystem abgelegt wird. Nachdem dieses Ergebnis wieder in die Datenbank importiert worden ist, ruft das Steuerprogramm eine geeignete Rekompositionsoperation auf, die die Daten mit den bereits rekomponierten Daten aus anderen Partitionen zusammensetzt und Konflikte auflo¨st. Anschließend kann das Steuerprogramm mit der na¨chsten Partition aus dem Partitionierungsschema fortfahren bis der komplette Datensatz bearbeitet ist.
Fu¨r Zugriffe auf die mo¨glicherweise großen Datensa¨tze innerhalb der Partitionierungs- und Rekompositionsoperationen verwenden wir konsequent SQL-Anweisungen. Dadurch machen wir implizit von den im ra¨umlichen Datenbanksystem implementierten externen Algorithmen Gebrauch, so dass innerhalb dieser Operationen eine effiziente Abfolge von I/O-Zugriffen erfolgt. Da innerhalb des Geoprogramms nur noch auf die Daten aus einer Partition zugegriffen wird, sind dort keine externen Algorithmen mehr no¨tig. 3.2
Um vorzugeben, wie geographische Daten bei der Partitionierung aufgeteilt werden, verwenden wir ein sogenanntes Partitionierungsschema. Dieses besteht aus einer schnittfreien und lu¨ckenlosen Menge von Polygonen (Partitionspolygone), denen jeweils eine eindeutige Partitionsnummer zugeordnet ist. Es ist mo¨glich, ein vordefiniertes Partitionierungsschema (z.B. eine Unterteilung in Verwaltungsbezirke), das in der Datenbank gespeichert ist, zu verwenden, oder den Partitionierungsdienst ein geeignetes Schema (z.B. ein Gitter aus gleich großen Rechtecken) erzeugen zu lassen.
Berechnungen in Geoprogrammen weisen oft eine mehr oder weniger starke Abha¨ngigkeit vom ra¨umlichen Kontext der Datenobjekte auf. Dies bedeutet, dass nur dann korrekte Ergebnisse in einem bestimmten Gebiet erzeugt werden ko¨nnen, wenn auch die Objekte aus einer lokalen Umgebung dieses Gebiets in der Partition enthalten sind. Bei einer streng disjunkten Aufteilung der geographischen Daten, wie durch das Partitionierungsschema vorgegeben, steht insbesondere fu¨r Objekte am Rand der Partition mo¨glicherweise nicht genug Kontext zur Verfu¨gung, da Objekte von außerhalb des Partitionspolygons beim Aufruf des Geoprogramms nicht in den Daten enthalten sind. Um diesen Nachteil zu kompensieren, erlauben es die von uns entwickelten Operationen, dass dieselben Datenobjekte in mehreren Partitionen enthalten sind, was wir als Redundanz bezeichnen. Das Ziel dabei ist es, dass beim Aufruf des Geoprogramms fu¨r eine Partition genug Daten in dieser enthalten sind, um korrekte Ergebnisse zumindest fu¨r alle Positionen innerhalb des Partitionspolygons zu berechnen.
Die Erzeugung von Redundanz in den partitionierten
Daten la¨sst sich auf verschiedene Arten erreichen. Eine
Mo¨glichkeit ist, die Partitionspolygone um einen festen Abstand
zu vergro¨ßern, so dass sich benachbarte Polygone am Rand
u¨berlappen. Diese Operation, die auch in Abbildung 2
dargestellt ist, bezeichnet man als Pufferbildung. In Abschnitt
4 geben wir weitere Mo¨glichkeiten an, bei denen redundant
zu repra¨sentierende Daten u¨ber die Beziehungen zwischen
den Objekten bestimmt werden. Zu beachten ist dabei, dass
sich in Abha¨ngigkeit davon, wieviel Redundanz man fu¨r eine
bestimmte Anwendung beno¨tigt, das Datenvolumen fu¨r
einzelne Partitionen vergro¨ßert. Im schlimmsten Fall kann eine
Partition dann mit dem zur Verfu¨gung stehenden
Hauptspeicher nicht mehr bearbeitet werden, wodurch das eigentliche
Ziel der Partitionierung verfehlt wird. Ha¨ufig kann man fu¨r
Geoprogramme nachweisen oder experimentell belegen, dass
die Abha¨ngigkeit vom Kontext auf Umgebungen mit kleiner
ra¨umlicher Ausdehnung beschra¨nkt bleibt (siehe z.B. [
Kontext
Datenobjekt
Partitionspolygon
lokale Berechnungen ausfu¨hren, und das in diesem Beitrag vorgestellte Konzept ist fu¨r solche Anwendungen einsetzbar.
Redundanz fu¨hrt dazu, dass fu¨r einige Datenobjekte mehrere Ergebnisse in unterschiedlichen Partitionen berechnet werden. Wir bezeichnen solche Situationen als Rekompositionskonflikte. Bei der Rekomposition mu¨ssen diese aufgelo¨st und die Ergebnisse wieder zu einem Gesamtdatensatz zusammengesetzt werden, der keine Spuren der Partitionierung mehr entha¨lt. Dabei sollen aus den Ergebnisdaten der Berechnung fu¨r eine Partition mo¨glichst immer die Objekte u¨bernommen werden, die sich innerhalb des Partitionspolygons befinden, da wir diese Ergebnisse als korrekt ansehen. Die aufgrund von fehlendem Kontext mo¨glicherweise fehlerbehafteten Ergebnisdaten außerhalb des Polygons sind zu verwerfen und aus dem Ergebnis der Partition zu u¨bernehmen, die diese Daten im Inneren entha¨lt. Unterschiedliche Rekompositionsoperationen werden insbesondere beno¨tigt, um verschiedene Konflikte zwischen ausgedehnten Objekten aufzulo¨sen, die die Grenze zwischen benachbarten Partitionen u¨berlappen. Beispiele passender Partitionierungs- und Rekompositionsoperationen fu¨r eine geographische Anwendung werden wir in Abschnitt 4 vorstellen. 3.3
Ein wesentliches Ziel beim Entwurf des Partitionierungsdienstes ist Flexibilita¨t. Die von diesem Dienst angebotenen Operationen zur Partitionierung und Rekomposition sollen fu¨r eine mo¨glichst große Vielfalt von Geoprogrammen anwendbar sein, um Berechnungen auf großen Datensa¨tzen zu ermo¨glichen. Geographische Daten ko¨nnen jedoch auf viele verschiedene Arten strukturiert sein. Das Datenbankschema fu¨r einen geographischen Datensatz bezeichnen wir im Folgenden als Repra¨sentationsmodell dieser Daten. Um trotz der Heterogenita¨t unterschiedlicher Repra¨sentationsmodelle nicht fu¨r jede Anwendung eigene Operationen anbieten zu mu¨ssen, identifizieren wir typische Strukturen bzw. Teilschemata, die in vielen Modellen auftreten. Sind die fu¨r eine Anwendung relevanten Informationen in einer solchen Struktur modelliert oder lassen sich in diese transformieren, ko¨nnen wir Operationen zur Partitionierung und Rekomposition einsetzen, die fu¨r ein solches Teilschema implementiert sind.
Der zentrale Teil des Schemas fu¨r einen geographischen Datensatz bildet ha¨ufig die in Abbildung 3 dargestellte Struktur. Die zu beschreibenden Merkmale der Erdoberfla¨che sind in den Daten durch Objekte dargestellt, die neben der ra¨umlichen Beschreibung durch eine Geometrie noch einen innerhalb des Datensatzes eindeutigen Identifikator und eine Objektart besitzen. Letztere legt fest, um was fu¨r einen Typ (z.B. Straße oder Ackerfla¨che) von Objekt es sich handelt. Zur feineren Charakterisierung der Objekte ko¨nnen weitere Attribute verwendet werden, wobei die erlaubten Typen von
Attributen ha¨ufig von der Objektart abha¨ngen (z.B. Breite der Fahrbahn fu¨r Straßen). Weiterhin beno¨tigt man Beziehungen zwischen den Objekten, die ebenfalls von unterschiedlichem Typ sein ko¨nnen, um z.B. U¨ ber- und Unterfu¨hrungen an Straßenkreuzungen zu modellieren.
Durch ein Repra¨sentationsmodell ko¨nnen fu¨r die
Geometrien der Objekte verschiedene Einschra¨nkungen festgelegt
sein, die es beim Partitionieren und Rekomponieren zu
beru¨cksichtigen gilt. Eine ha¨ufige Einschra¨nkung betrifft z.B.
den Geometrietyp, wenn nur Punkte, Linien oder Fla¨chen in
einem Datensatz enthalten sind. Weitere gebra¨uchliche
Einschra¨nkungen sind die Forderung der Schnittfreiheit, d.h.
Geometrien verschiedener Objekte du¨rfen sich nur an den
Ra¨ndern u¨berschneiden, oder das Verbot von Lu¨cken, so
dass der komplette Datenraum durch Fla¨chenobjekte
u¨berdeckt sein muss. Ein Beispiel fu¨r Repra¨sentationsmodelle
mit solchen Einschra¨nkungen sind Landbedeckungsdaten [
Repra¨sentationsmodelle mit linien- oder fla¨chenhaften
Geometrien, die nicht schnittfrei sind, werden ein wenig
abwertend auch als Spaghetti-Datenmodelle bezeichnet [
Abb. 4: Datenstruktur eines TDMs ab und ko¨nnen außerdem die Endpunkte von Kanten darstellen. Kanten wiederum repra¨sentieren linienhafte Objekte und bilden die Ra¨nder von Maschen. Und solche Maschen entsprechen Teilen von fla¨chenhaften Objekten. Die drei Mengen verschiedenartiger TDM-Elemente sind jeweils schnittfrei, allerdings ko¨nnen ein Knoten oder eine Kante in einer Masche enthalten sein. Ein geographisches Objekt ist durch die TDM-Elemente repra¨sentiert, durch deren Aggregation man die Geometrie des Objekts rekonstruieren kann. Dabei kann dasselbe Element (z.B. eine Kante) zu mehreren Objekten geho¨ren und repra¨sentiert in diesem Fall einen gemeinsamen Bestandteil der Geometrien der Objekte, der folglich im Gegensatz zum Spaghetti-Modell nur einmal abgespeichert werden muss. Ein weiterer Unterschied besteht darin, dass im TDM die topologischen Beziehungen der Elemente zueinander explizit gespeichert werden. Dadurch ko¨nnen z.B. benachbarte Fla¨chen bestimmt werden, ohne dass man geometrische Berechnungen durchfu¨hren muss.
Weitere typische Schemata werden bei der Integration von
Daten verwendet, um Zuordnungen von Objekten aus
unterschiedlichen Datensa¨tzen zu modellieren [
Als anschauliches Beispiel fu¨r die Verwendung
unterschiedlicher Partitionierungs- und Rekompositionsoperationen
betrachten wir in diesem Abschnitt das geometrische Problem
der Liniensegmentierung. Dieses besteht darin, eine
Menge von Linienobjekten, die sich beliebig u¨berschneiden
du¨rfen, in eine schnittfreie Menge von Linien zu
transformieren. Es gibt eine Reihe von nu¨tzlichen Anwendungen, wie
z.B. zur Erzeugung der Menge von Kanten bei der
Transformation von Spaghetti-Daten in ein topologisches
Datenmodell. Die hier verwendete Implementierung besteht aus
zwei Schritten. Zuerst werden mit Hilfe eines
Plane-SweepVerfahrens [
Im Folgenden stellen wir fu¨r die Liniensegmentierung drei
Strategien zur Partitionierung und Rekomposition aus dem
in Abschnitt 3 beschriebenen Partitionierungsdienst vor. Es
sei angemerkt, dass die fu¨r diese Strategien angebotenen
Datenbankprozeduren in der Anwendbarkeit nicht auf dieses
eine Problem eingeschra¨nkt sind, sondern sich auch fu¨r viele
weitere Geoprogramme einsetzen lassen. Beispielsweise
wurde Variante 1 bereits in [
Wir wa¨hlen in dieser Variante fu¨r eine Partition alle Objekte aus, deren Geometrien sich mit dem Partitionspolygon u¨berschneiden. Zusa¨tzlich schneiden wir bei Objekten am Rand der Partition den Teil der Geometrie ab, der u¨ber das Partitionspolygon herausragt. Folglich verbleibt nur der innerhalb des Partitionspolygons liegende Anteil als geometrische Repra¨sentation des Objekts in der Partition. Dies wird allgemein auch als Clipping bezeichnet. Durch diese Art von Aufteilung kann ein Linienobjekt ggf. in mehreren Partitionen auftreten, allerdings jeweils mit einem unterschiedlichen Teil seiner Geometrie, weshalb wir die Partitionierung als disjunkt bezeichnen ko¨nnen. Bei der Liniensegmentierung fu¨r eine Partition werden alle Schnitte von Objekten gefunden, die innerhalb des Partitionspolygons liegen, und die Geometrien entsprechend aufgeteilt.
Betrachtet man die Ergebnisse der Liniensegmentierung fu¨r die einzelnen Partitionen gemeinsam, fa¨llt auf, dass neben den korrekten Unterteilungen an den Linienschnittpunkten zusa¨tzlich Unterteilungen an den Schnittpunkten mit den Ra¨ndern der Partitionen auftreten, was auf das Clipping zuru¨ckzufu¨hren ist. Man betrachte z.B. die Situation in Abbildung 5, in der aus drei Linienobjekten a, b und c
insgesamt acht segmentierte Linien erzeugt wurden. Bei der Unterteilung zwischen a2 und a3 liegt allerdings kein echter Schnitt vor. Da derartige Situationen ohne Partitionierung nicht auftreten wu¨rden, liegen hier Rekompositionskonflikte vor und mu¨ssen durch eine geeignete Operation bereinigt werden. Dazu bestimmen wir, welche Linien aus dem bereits zusammengesetzten Ergebnis welche anderen Linien aus der aktuellen Partition an der Partitionsgrenze beru¨hren und fu¨gen diese durch eine Vereinigung zu einer Linie zusammen.
Wir mu¨ssen allerdings auch beru¨cksichtigen, dass ein Linienobjekt aus dem Ausgangsdatensatz mehrmals den Rand der Partition schneiden kann, weshalb wir ggf. auch Gruppen von mehr als zwei Linien zu einem Objekt vereinigen mu¨ssen. Ein weiterer Sonderfall liegt vor, wenn sich zwei Linien aus dem Ausgangsdatensatz genau auf dem Rand eines Partitionspolygons u¨berschneiden, weil es sich dann bei dem nach obiger Vorschrift ermittelten Beru¨hrungspunkt um einen echten Schnittpunkt handelt und somit keine Vereinigung stattfinden darf. Wir ko¨nnen diese Situationen dadurch erkennen, dass sich zwei segmentierte Linien aus derselben Partition an einem solchen Punkt beru¨hren. 4.2
Wie in der ersten Variante wa¨hlen wir alle Objekte aus, die das Partitionspolygon schneiden, verzichten aber auf Clipping. Die Intention dabei ist es, aufwa¨ndige Berechnungen zum Abschneiden und Vereinigen der Geometrien einzusparen. Dafu¨r nehmen wir etwas Redundanz in Kauf, denn Linien aus dem Ausgangsdatensatz, die u¨ber den Rand der Partition hinausragen, werden in mehreren Partitionen mit ihrer vollsta¨ndigen Geometrie repra¨sentiert, so dass eine nicht disjunkte Partitionierung vorliegt. Schnitte zwischen solchen Objekten werden demnach bei der Segmentierung mehrfach in unterschiedlichen Partitionen berechnet.
Beim Rekomponieren einer Partition mu¨ssen Duplikate aus den Ergebnissen entfernt werden, da die aus den mehrfach repra¨sentierten Objekten gebildeten Linien auch mehrfach in den Ergebnissen auftreten. Allerdings stimmen diese Duplikate in Bezug auf die Segmentierung nicht zwingend u¨berein, denn der Schnitt einer u¨ber den Rand der Partition hinausragenden Linie mit einer Linie, die komplett außerhalb der Partition liegt, wird bei der Berechnung in dieser Partition nicht gefunden. Man betrachte z.B. die Situation in Abbildung 6. Wa¨hrend im Ergebnis der linken Partition (cyan) die Linie a am Schnittpunkt mit b in a1 und a2 unterteilt wurde, fehlt die Unterteilung am Schnittpunkt mit c. Fu¨r das Ergebnis der rechten Partition (magenta) hingegen ist die Situation genau umgekehrt.
Um Duplikate zu entfernen, verwerfen wir beim Rekomponieren einer Partition zuna¨chst alle Linien, die komplett außerhalb des Partitionspolygons liegen, denn diese sind entweder bereits im Ergebnis enthalten oder werden beim Rekomponieren einer der na¨chsten Partitionen eingefu¨gt. Fu¨r Situationen wie in Abbildung 6 bestimmen wir fu¨r die sich u¨berlappenden Linien den gemeinsamen Teil durch eine geometrische Durchschnittsoperation. Z.B. fu¨gen wir anstelle der zu langen Linien a2 und a3 nur deren Durchschnitt ins Gesamtergebnis ein. 4.3
Im Vergleich zur vorigen Variante ko¨nnen wir die Eliminierung der Duplikate bei der Rekomposition weiter vereinfachen, wenn wir bei der Partitionierung noch mehr Redundanz hinzufu¨gen. Wir bezeichnen dazu die Linienobjekte, die das Polygon der Partition p schneiden, als p-Objekte. Um alle p-Objekte bei der Berechnung fu¨r diese Partition korrekt zu segmentieren, mu¨ssen wir bei der Partitionierung noch Linien von außerhalb der Partition hinzunehmen, die sich mit einem p-Objekt u¨berschneiden.
Dadurch, dass bei der Partitionierung mehr Objekte redundant fu¨r mehrere Partitionen ausgewa¨hlt werden, entstehen auch mehr Duplikate, die bei der Rekomposition entfernt werden mu¨ssen (siehe Abbildung 7). Die meisten dieser Duplikate werden wir wieder los, indem wir (wie bei Variante 2) Linien außerhalb des Partitionspolygons verwerfen (z.B. a′1/a′4). Bei allen Linien im Ergebnis einer Partition, die den Rand des Partitionspolygons schneiden, ko¨nnen allerdings in dieser Variante nur echt u¨bereinstimmende Duplikate auftreten, denn diese Linien wurden vollsta¨ndig segmentiert. Anstatt Durchschnitte zu berechnen, reicht es somit aus, von den am Rand der Partition auftretenden Duplikaten (hier a2/a3) jeweils ein Objekt ins Ergebnis zu u¨bernehmen. a1 a' 1 b1 b'1 a2 b2 b'2 a3 c'1 c1 a' 4 a4 c'2 c2
Um die Anwendbarkeit der in Abschnitt 4 vorgestellten Partitionierungs- und Rekompositionsoperationen zu demonstrieren und die Varianten miteinander zu vergleichen, fu¨hren wir Tests mit einem ca. 7,2GB großen kommerziell produzierten Datensatz durch, der das gesamte Bundesland Hessen umfasst. Diese Daten enthalten Informationen u¨ber Straßen und weitere fu¨r den Kraftfahrzeugverkehr relevante geographische Objekte in Form von Liniengeometrien, die fu¨r die kartographische Darstellung optimiert und insbesondere nicht schnittfrei sind. Partitionierung und Rekomposition sind in einer Datenbank (Oracle 11g) mit ra¨umlicher Erweiterung (Oracle Spatial) implementiert. Zur Segmentierung verwenden wir ein Programm aus einer Java-Bibliothek fu¨r geometrische Berechnungen (JTS Topology Suite), das durch zahlreiche Optimierungen auf Kosten eines hohen Speicherverbrauchs sehr effizient arbeitet.
Wir fu¨hren fu¨r diesen Datensatz mit jeder der drei Varianten eine Segmentierung durch, wobei wir ein Partitionierungsschema aus 129 Quadraten mit jeweils 25km Kantenla¨nge verwenden. Wir messen und summieren dabei jeweils separat die Laufzeiten, die bei der Partitionierung, Segmentierung und Rekomposition fu¨r alle Partitionen beno¨tigt werden. Diese Laufzeiten sind in Abbildung 8 dargestellt. Die Laufzeit fu¨r die Segmentierung ist erwartungsgema¨ß in
der ersten Variante am geringsten und steigt durch das Hinzufu¨gen von mehr Redundanz in Variante 2 und 3 jeweils leicht an. Am meisten Zeit beno¨tigt in allen Varianten die Rekomposition. Wa¨hrend diese in Variante 3 die geringste Laufzeit beno¨tigt, ist dabei jedoch eine vergleichsweise aufwa¨ndige Partitionierung no¨tig. Die beste Gesamtlaufzeit hat somit Variante 2, bei der die Partitionierung am schnellsten geht und die Zeiten fu¨r Segmentierung und Rekomposition jeweils in der Mitte liegen.
Der in diesem Beitrag vorgestellte Partitionierungsdienst fu¨r geographische Daten in ra¨umlichen Datenbanken besteht im Wesentlichen aus einer Sammlung von flexibel anwendbaren Partitionierungs- und Rekompositionsoperationen. Diese erlauben es, Geoprogramme mit sehr geringem Entwicklungsaufwand fit fu¨r die Bearbeitung großer Datenmengen zu machen. Dabei bleibt die Freiheit der Wahl einer Programmiersprache und von Software-Bibliotheken sowie die gute Wartbarkeit der Geoprogramme erhalten, da Zugriffe auf extern gespeicherte Daten nur wa¨hrend der Partitionierung und Rekomposition erfolgen mu¨ssen. Neben dem an dieser Stelle vorgestellten Anwendungsbeispiel eignet sich diese Vorgehensweise fu¨r eine Vielzahl weiterer geographischer Problemstellungen, sofern diese durch hinreichend lokale Algorithmen gelo¨st werden ko¨nnen, so dass die beno¨tigte Redundanz bei der Partitionierung nicht zu groß wird.
Wa¨hrend fu¨r die in diesem Beitrag vorgestellten Experimente die Gro¨ße der Partitionen fest vorgegeben wurde, ist es fu¨r einen Anwender des Partitionierungsdienstes wu¨nschenswert, stattdessen die Gro¨ße des verfu¨gbaren Speichers angeben zu ko¨nnen, fu¨r die der Dienst dann ein geeignetes Partitionierungsschema berechnet. Daher arbeiten wir daran, Modelle aus der Literatur zum Scha¨tzen der Partitionsgro¨ße fu¨r ra¨umliche Verbunde zu verallgemeinern, um diese auch auf andere Geoprogramme anwenden zu ko¨nnen. Dabei muss auch beru¨cksichtigt werden, dass reale geographische Daten nicht gleichma¨ßig verteilt sind, und somit auch die Partitionsgro¨ße innerhalb eines Partitionierungsschemas abha¨ngig von der Datendichte variieren sollte.
Um das Spektrum von mo¨glichen Anwendungen fu¨r den Partitionierungsdienst zu vergro¨ßern, muss dieser um weitere Operationen und insbesondere weitere Repra¨sentationsmodelle erweitert werden. Außerdem werden wir genauer untersuchen, wie sich dieser Dienst mo¨glichst gewinnbringend fu¨r die Fortfu¨hrung von abgeleiteten Datensa¨tzen einsetzen la¨sst. Dieser Ansatz basiert auf der Idee, bei Updates fu¨r Geobasisdaten zuna¨chst mo¨glichst kleine, aber ra¨umlich zusammenha¨ngende Gebiete zu identifizieren, in denen A¨ nderungen stattgefunden haben. Fu¨r die Aktualisierung von abgeleiteten Datensa¨tzen mu¨ssen dann unter Verwendung von Partitionierung und Rekomposition nur diese Gebiete an Stelle des kompletten Datensatzes neu berechnet werden. 7.
Diese Arbeit wurde vom Bundesamt fu¨r Kartographie und Geoda¨sie im Rahmen des Projekts Wissensbasierter Photogrammetrisch-Kartographischer Arbeitsplatz (WiPKA) gefo¨rdert.