=Paper=
{{Paper
|id=None
|storemode=property
|title=Ein Partitionierungsdienst für Geographische Daten in Räumlichen Datenbanken
|pdfUrl=https://ceur-ws.org/Vol-850/paper_warneke.pdf
|volume=Vol-850
|dblpUrl=https://dblp.org/rec/conf/gvd/WarnekeL12
}}
==Ein Partitionierungsdienst für Geographische Daten in Räumlichen Datenbanken==
https://ceur-ws.org/Vol-850/paper_warneke.pdf
Ein Partitionierungsdienst für Geographische Daten in
Räumlichen Datenbanken
Hendrik Warneke und Udo W. Lipeck
Institut für Praktische Informatik, FG Datenbanken und Informationssysteme
Leibniz Universität Hannover, Welfengarten 1, 30159 Hannover
{hwa,ul}@dbs.uni-hannover.de
ZUSAMMENFASSUNG tenproduzenten, Dienstleister und Nutzer über Netzwerke,
Da in der computergestützten Geographie mit zum Teil sehr in der Regel das Internet, miteinander verknüpft sind und
großen Mengen von räumlichen Daten gearbeitet werden geographische Informationen mit standardisierten Verfahren
muss, hat sich mittlerweile die Überzeugung durchgesetzt, austauschen und verarbeiten [4]. Diese Strukturen sehen vor,
solche Datensätze in räumlichen Datenbanken zu speichern. dass geographische Daten blattschnittfrei in räumlichen Da-
Allerdings wird bei der Entwicklung von geographischen Pro- tenbanken gespeichert werden, wozu man häufig objektrela-
grammen dem Aspekt der Skalierbarkeit oftmals wenig Be- tionale Systeme mit Erweiterungen um räumliche Datenty-
achtung geschenkt. So enthalten verbreitete Programme für pen, Operatoren und Indexe einsetzt.
Geoinformationssysteme wenig bis keine sogenannten exter- Aus den grundlegenden, mit den Techniken der Landes-
nen Algorithmen, die den Geschwindigkeitsunterschied zwi- vermessung hergestellten Daten, den sogenannten Geobasis-
schen internem (RAM) und externem Speicher (Festplatte) daten, können durch vielfältige Prozesse neue Datensätze
berücksichtigen und versuchen, die Anzahl der I/O-Zugriffe abgeleitet werden, die man für kartographische Darstellun-
auf letzteren zu minimieren. Diese Programme arbeiten da- gen von Informationen aus Fachbereichen wie z.B. Verkehr,
her nur dann effizient, wenn genug interner Speicher für die Umwelt und Ökonomie verwendet. Die folgende Auflistung
zu bearbeitenden Geodaten zur Verfügung steht. Wir stel- enthält einige Beispiele für Klassen solcher Prozesse, die heu-
len in diesem Beitrag einen auf Partitionierung basierenden te meistens automatisiert durch Computerprogramme, im
Ansatz vor, der den Aufwand für die Entwicklung von auf folgenden Geoprogramme genannt, durchgeführt werden.
großen Geodatenmengen skalierenden Programmen stark re- Generalisierung: Um eine lesbare Kartendarstellung aus
duziert. Dazu werden Zugriffe auf externe Speicher in eine den Geobasisdaten zu erzeugen, müssen diese durch
vorgelagerte Partitionierungs- und eine nachgelagerte Re- Operationen wie z.B. das Weglassen von Objekten so-
kompositionsphase verschoben und für diese Phasen flexible wie Vereinfachen, Zusammenfassen oder Verdrängen
Operationen, die ein breites Spektrum an geographischen von Geometrien verändert werden. Dabei besitzen die
Problemstellungen unterstützen, als Partitionierungsdienst Basisdaten meist eine höhere Auflösung als für die be-
für räumliche Datenbanksysteme angeboten. absichtigte Darstellung benötigt wird.
Transformation: Erfordert eine Anwendung ein bestimm-
1. EINLEITUNG tes Datenmodell, das sich von dem der Geobasisdaten
Lange Zeit verwendete man für die Arbeit mit geogra- unterscheidet, müssen diese zunächst in das beabsich-
phischen Informationen größtenteils auf Papier gedruckte tigte Modell transformiert werden.
Landkarten. Diese wurden in handliche Kartenblätter unter-
teilt, um die zur Beschreibung der Erdoberfläche in hoher Integration: Um Informationen aus verschiedenen Daten-
Auflösung benötigten Datenmengen besser handhaben zu sätzen gemeinsam nutzen zu können, werden diese zu
können. Der Übergang zu computergestützten Geoinforma- einem Datensatz integriert. Dies erfordert z.B. Verfah-
tionssystemen erlaubte es, Geodaten mit Hilfe unabhängig ren wie die Identifikation korrespondierender geogra-
vom Maßstab in Form von Geometrien zu modellieren. Da- phischer Objekte (Matching) sowie die Anpassung von
bei behielt man häufig die Aufteilung in Kartenblätter auf Geometrien für die gemeinsame Darstellung.
Dateiebene bei, da die verarbeitbare Datenmenge für vie-
le Systeme und Datenformate beschränkt war. Heute baut Geoprogramme, die diese Prozesse implementieren, müssen
man sogenannte Geodateninfrastrukturen auf, in denen Da- aufgrund des beträchtlichen Umfangs von Geobasisdaten-
sätzen in der Lage sein, den begrenzten Hauptspeicher ei-
nes Rechners effizient zu verwalten, um Performanceproble-
me aufgrund von Swapping oder Programmabstürze wegen
Speichermangels zu vermeiden. Dazu würde es sich anbie-
ten, diese Programme als Datenbankanwendungen zu im-
plementieren, die sämtliche Datenzugriffe über SQL-Befehle
abwickeln. Dieses Vorgehen ist jedoch mit einigen Nachtei-
len verbunden. Zunächst ist man auf die von dem räumli-
24th GI-Workshop on Foundations of Databases (Grundlagen von Daten-
banken), 29.05.2012 - 01.06.2012, Lübbenau, Germany. chen Datenbanksystem angebotene Funktionalität für geo-
Copyright is held by the author/owner(s). metrische und geographische Berechnungen beschränkt. Die
freie Auswahl aus spezialisierten und optimierten Software- Repräsentationen der Daten weitergegeben werden. Für un-
Bibliotheken entfällt. Weiterhin hängt die Performance von seren Partitionierungsdienst sind wir hingegen an flexiblen
SQL-basierten Anwendungen entscheidend von der Quali- Partitionierungs- bzw. Rekompositionsoperationen interes-
tät der Anfrageoptimierung ab. Aufgrund der inhärenten siert, die für die Entwicklung der Geoprogramme keine ein-
Schwierigkeit der Kostenschätzung für geometrische Opera- schränkenden Vorgaben machen.
tionen stellt dies insbesondere bei räumlichen Datenbanken Aufgrund seiner Wichtigkeit bei der Berechnung räum-
ein Problem dar. Schließlich müssten die Algorithmen für licher Verbunde ist das Problem der Bestimmung von sich
Geoprogramme in eine relationale Formulierung umgewan- überschneidenden achsenparallelen Rechtecken besonders in-
delt werden, was aufgrund von deren Komplexität i.A. auf- tensiv untersucht worden. Während für interne Algorithmen
wändig und fehleranfällig ist. Hinzu kommt noch, dass die das Plane-Sweep-Paradigma [1] favorisiert wird, verwenden
Entwickler geographischer Anwendungen oftmals keine Da- externe oder parallele Algorithmen häufig Partitionierung,
tenbankspezialisten sind. wie z.B. Patel und DeWitt [5]. Der Einfluss von Redundanz
Wir stellen in diesem Beitrag einen Ansatz vor, der die- auf die Laufzeit von partitionierungsbasierten Algorithmen
se Probleme durch Partitionierung der Geobasisdaten um- für dieses Problem wird beispielsweise von Zhou et.al. [8] un-
geht. Statt ein Geoprogramm auf den gesamten Datensatz tersucht. In einer ähnlichen Untersuchung [2] kommen Dit-
anzuwenden, wird jede Datenpartition für sich allein bear- trich und Seeger u.a. zu dem auf den ersten Blick überra-
beitet, wobei diese so klein gewählt wird, dass der verfüg- schenden Ergebnis, dass man durch mehr Redundanz in den
bare Hauptspeicher nicht überfüllt wird. Die für die ein- Berechnungen sogar die Laufzeit verbessern kann.
zelnen Partitionen berechneten Ergebnisdatensätze müssen
anschließend wieder zu einem Gesamtdatensatz zusammen- 3. ENTWURF DES PARTITIONIERUNGS-
gesetzt werden, was wir als Rekomposition bezeichnen. Da
unterschiedliche Prozesse auch unterschiedliche Strategien DIENSTES
für die Partitionierung und Rekomposition erfordern, bieten
wir eine Sammlung solcher Operationen als Dienst auf einem 3.1 Architektur
räumlichen Datenbanksystem an. Die Entwickler von Geo- Wir implementieren Partitionierungs- und Rekompositi-
programmen können diesen über eine einfache Schnittstelle onsoperationen als Stored Procedures auf einem räumlichen
ansprechen, wodurch die Notwendigkeit entfällt, innerhalb Datenbanksystem. Diese können über eine Datenbankschnitt-
der Programme selbst den Austausch der Daten zwischen stelle von einem Steuerprogramm außerhalb der Datenbank
Haupt- und sekundärem Speicher zu berücksichtigen. aufgerufen werden, um in der Datenbank gespeicherte Da-
Für geographische Daten bietet es sich an, zur Partitio- ten für ein Geoprogramm aufzuteilen und wieder zusammen-
nierung die räumliche Lage zu verwenden und Datenobjek- zusetzen (Abbildung 1). Das Steuerprogramm liest jeweils
te aus einem zusammenhängenden Gebiet in eine Partition
einzuteilen. Dieser Ansatz ist allgemein für Geoprogramme
anwendbar, die sich lokal verhalten. Dies bedeutet, dass für
die Berechnung von Ergebnissen an einer Position nur Da-
ten aus einer begrenzten Umgebung benötigt werden und
diese Umgebung klein gegenüber einer Partition ist. In die-
sem Fall lassen sich Fehler, die insbesondere am Rand einer
Partition entstehen, weil dem Geoprogramm nicht alle Da-
ten zur Verfügung stehen, reduzieren oder ganz vermeiden,
indem man sich überlappende Partitionen erzeugt [6].
Der Rest des Beitrags ist wie folgt strukturiert: In Ab-
schnitt 2 nennen wir Arbeiten, die mit unserem Ansatz ver-
wandt sind. Abschnitt 3 beschreibt die Architektur und das
Funktionsprinzip des Partitionierungsdienstes. In Abschnitt
4 verwenden wir die Liniensegmentierung als konkretes An-
wendungsbeispiel und geben für diesen Prozess alternative
Partitionierungs- und Rekompositionsoperationen an. Ab-
schnitt 5 beschreibt die Ergebnisse von Experimenten mit
diesen Operationen auf realen geographischen Daten. Schließ-
lich liefert Abschnitt 6 ein Fazit über den in diesem Beitrag Abb. 1: Geoprogramm (Ablauf ) mit Partitionierung
vorgestellten Ansatz und einen Ausblick auf Folgearbeiten.
einen Eintrag aus dem Partitionierungsschema (Abschnitt
2. VERWANDTE ARBEITEN 3.2), das die Geometrien der Partitionen enthält. Damit wird
Das Prinzip, Datensätze zuerst aufzuteilen, Teilergebnis- eine geeignete Partitionierungsoperation aufgerufen und ei-
se zu berechnen und später aus den Teilergebnissen ein Ge- ne Partition der Ausgangsdaten berechnet. Diese muss in ein
samtergebnis zu generieren, ist in der Informatik unter dem von dem Geoprogramm verwendetes Dateiformat exportiert
Namen Divide-and-Conquer bekannt. Auch für geometrische werden, bevor dieses vom Steuerprogramm aufgerufen wird,
Probleme gibt es eine Reihe von Vorschlägen, beispielsweise um für die Datenpartition ein Ergebnis zu berechnen, das
von Güting und Schilling [3], die externe Algorithmen nach zunächst ebenfalls im Dateisystem abgelegt wird. Nachdem
diesem Prinzip entwickeln. Um eine optimale asymptotische dieses Ergebnis wieder in die Datenbank importiert worden
Laufzeit zu erreichen, werden die drei Teilschritte stark auf- ist, ruft das Steuerprogramm eine geeignete Rekompositi-
einander abgestimmt, indem z.B. Sortierungen oder spezielle onsoperation auf, die die Daten mit den bereits rekompo-
nierten Daten aus anderen Partitionen zusammensetzt und
Konflikte auflöst. Anschließend kann das Steuerprogramm Pufferpolygon
mit der nächsten Partition aus dem Partitionierungsschema
fortfahren bis der komplette Datensatz bearbeitet ist.
Für Zugriffe auf die möglicherweise großen Datensätze in- Kontext Datenobjekt
nerhalb der Partitionierungs- und Rekompositionsoperatio-
Partitionspolygon
nen verwenden wir konsequent SQL-Anweisungen. Dadurch
machen wir implizit von den im räumlichen Datenbanksys-
tem implementierten externen Algorithmen Gebrauch, so
dass innerhalb dieser Operationen eine effiziente Abfolge von Abb. 2: Kontext, Partitions- und Pufferpolygon
I/O-Zugriffen erfolgt. Da innerhalb des Geoprogramms nur
noch auf die Daten aus einer Partition zugegriffen wird, sind
dort keine externen Algorithmen mehr nötig. lokale Berechnungen ausführen, und das in diesem Beitrag
vorgestellte Konzept ist für solche Anwendungen einsetzbar.
3.2 Redundanz Redundanz führt dazu, dass für einige Datenobjekte meh-
Um vorzugeben, wie geographische Daten bei der Parti- rere Ergebnisse in unterschiedlichen Partitionen berechnet
tionierung aufgeteilt werden, verwenden wir ein sogenanntes werden. Wir bezeichnen solche Situationen als Rekomposi-
Partitionierungsschema. Dieses besteht aus einer schnittfrei- tionskonflikte. Bei der Rekomposition müssen diese aufge-
en und lückenlosen Menge von Polygonen (Partitionspoly- löst und die Ergebnisse wieder zu einem Gesamtdatensatz
gone), denen jeweils eine eindeutige Partitionsnummer zu- zusammengesetzt werden, der keine Spuren der Partitionie-
geordnet ist. Es ist möglich, ein vordefiniertes Partitionie- rung mehr enthält. Dabei sollen aus den Ergebnisdaten der
rungsschema (z.B. eine Unterteilung in Verwaltungsbezir- Berechnung für eine Partition möglichst immer die Objekte
ke), das in der Datenbank gespeichert ist, zu verwenden, übernommen werden, die sich innerhalb des Partitionspoly-
oder den Partitionierungsdienst ein geeignetes Schema (z.B. gons befinden, da wir diese Ergebnisse als korrekt ansehen.
ein Gitter aus gleich großen Rechtecken) erzeugen zu lassen. Die aufgrund von fehlendem Kontext möglicherweise fehler-
Berechnungen in Geoprogrammen weisen oft eine mehr behafteten Ergebnisdaten außerhalb des Polygons sind zu
oder weniger starke Abhängigkeit vom räumlichen Kontext verwerfen und aus dem Ergebnis der Partition zu überneh-
der Datenobjekte auf. Dies bedeutet, dass nur dann korrekte men, die diese Daten im Inneren enthält. Unterschiedliche
Ergebnisse in einem bestimmten Gebiet erzeugt werden kön- Rekompositionsoperationen werden insbesondere benötigt,
nen, wenn auch die Objekte aus einer lokalen Umgebung die- um verschiedene Konflikte zwischen ausgedehnten Objekten
ses Gebiets in der Partition enthalten sind. Bei einer streng aufzulösen, die die Grenze zwischen benachbarten Partitio-
disjunkten Aufteilung der geographischen Daten, wie durch nen überlappen. Beispiele passender Partitionierungs- und
das Partitionierungsschema vorgegeben, steht insbesondere Rekompositionsoperationen für eine geographische Anwen-
für Objekte am Rand der Partition möglicherweise nicht ge- dung werden wir in Abschnitt 4 vorstellen.
nug Kontext zur Verfügung, da Objekte von außerhalb des
Partitionspolygons beim Aufruf des Geoprogramms nicht in 3.3 Repräsentationsmodelle
den Daten enthalten sind. Um diesen Nachteil zu kompen- Ein wesentliches Ziel beim Entwurf des Partitionierungs-
sieren, erlauben es die von uns entwickelten Operationen, dienstes ist Flexibilität. Die von diesem Dienst angebotenen
dass dieselben Datenobjekte in mehreren Partitionen ent- Operationen zur Partitionierung und Rekomposition sollen
halten sind, was wir als Redundanz bezeichnen. Das Ziel für eine möglichst große Vielfalt von Geoprogrammen an-
dabei ist es, dass beim Aufruf des Geoprogramms für eine wendbar sein, um Berechnungen auf großen Datensätzen zu
Partition genug Daten in dieser enthalten sind, um korrek- ermöglichen. Geographische Daten können jedoch auf viele
te Ergebnisse zumindest für alle Positionen innerhalb des verschiedene Arten strukturiert sein. Das Datenbankschema
Partitionspolygons zu berechnen. für einen geographischen Datensatz bezeichnen wir im Fol-
Die Erzeugung von Redundanz in den partitionierten Da- genden als Repräsentationsmodell dieser Daten. Um trotz
ten lässt sich auf verschiedene Arten erreichen. Eine Mög- der Heterogenität unterschiedlicher Repräsentationsmodelle
lichkeit ist, die Partitionspolygone um einen festen Abstand nicht für jede Anwendung eigene Operationen anbieten zu
zu vergrößern, so dass sich benachbarte Polygone am Rand müssen, identifizieren wir typische Strukturen bzw. Teilsche-
überlappen. Diese Operation, die auch in Abbildung 2 dar- mata, die in vielen Modellen auftreten. Sind die für eine An-
gestellt ist, bezeichnet man als Pufferbildung. In Abschnitt wendung relevanten Informationen in einer solchen Struktur
4 geben wir weitere Möglichkeiten an, bei denen redundant modelliert oder lassen sich in diese transformieren, können
zu repräsentierende Daten über die Beziehungen zwischen wir Operationen zur Partitionierung und Rekomposition ein-
den Objekten bestimmt werden. Zu beachten ist dabei, dass setzen, die für ein solches Teilschema implementiert sind.
sich in Abhängigkeit davon, wieviel Redundanz man für eine Der zentrale Teil des Schemas für einen geographischen
bestimmte Anwendung benötigt, das Datenvolumen für ein- Datensatz bildet häufig die in Abbildung 3 dargestellte Struk-
zelne Partitionen vergrößert. Im schlimmsten Fall kann eine tur. Die zu beschreibenden Merkmale der Erdoberfläche sind
Partition dann mit dem zur Verfügung stehenden Hauptspei- in den Daten durch Objekte dargestellt, die neben der räum-
cher nicht mehr bearbeitet werden, wodurch das eigentliche lichen Beschreibung durch eine Geometrie noch einen inner-
Ziel der Partitionierung verfehlt wird. Häufig kann man für halb des Datensatzes eindeutigen Identifikator und eine Ob-
Geoprogramme nachweisen oder experimentell belegen, dass jektart besitzen. Letztere legt fest, um was für einen Typ
die Abhängigkeit vom Kontext auf Umgebungen mit kleiner (z.B. Straße oder Ackerfläche) von Objekt es sich handelt.
räumlicher Ausdehnung beschränkt bleibt (siehe z.B. [6]). Zur feineren Charakterisierung der Objekte können weitere
In diesen Fällen sprechen wir davon, dass diese Programme Attribute verwendet werden, wobei die erlaubten Typen von
folglich im Gegensatz zum Spaghetti-Modell nur einmal ab-
gespeichert werden muss. Ein weiterer Unterschied besteht
darin, dass im TDM die topologischen Beziehungen der Ele-
mente zueinander explizit gespeichert werden. Dadurch kön-
nen z.B. benachbarte Flächen bestimmt werden, ohne dass
Abb. 3: Objekte, Attribute und Beziehungen man geometrische Berechnungen durchführen muss.
Weitere typische Schemata werden bei der Integration von
Daten verwendet, um Zuordnungen von Objekten aus unter-
Attributen häufig von der Objektart abhängen (z.B. Brei- schiedlichen Datensätzen zu modellieren [7]. Wir verzichten
te der Fahrbahn für Straßen). Weiterhin benötigt man Be- aus Platzgründen auf eine detaillierte Beschreibung.
ziehungen zwischen den Objekten, die ebenfalls von unter-
schiedlichem Typ sein können, um z.B. Über- und Unterfüh-
rungen an Straßenkreuzungen zu modellieren. 4. ANWENDUNGSBEISPIEL
Durch ein Repräsentationsmodell können für die Geome- Als anschauliches Beispiel für die Verwendung unterschied-
trien der Objekte verschiedene Einschränkungen festgelegt licher Partitionierungs- und Rekompositionsoperationen be-
sein, die es beim Partitionieren und Rekomponieren zu be- trachten wir in diesem Abschnitt das geometrische Problem
rücksichtigen gilt. Eine häufige Einschränkung betrifft z.B. der Liniensegmentierung. Dieses besteht darin, eine Men-
den Geometrietyp, wenn nur Punkte, Linien oder Flächen in ge von Linienobjekten, die sich beliebig überschneiden dür-
einem Datensatz enthalten sind. Weitere gebräuchliche Ein- fen, in eine schnittfreie Menge von Linien zu transformie-
schränkungen sind die Forderung der Schnittfreiheit, d.h. ren. Es gibt eine Reihe von nützlichen Anwendungen, wie
Geometrien verschiedener Objekte dürfen sich nur an den z.B. zur Erzeugung der Menge von Kanten bei der Trans-
Rändern überschneiden, oder das Verbot von Lücken, so formation von Spaghetti-Daten in ein topologisches Daten-
dass der komplette Datenraum durch Flächenobjekte über- modell. Die hier verwendete Implementierung besteht aus
deckt sein muss. Ein Beispiel für Repräsentationsmodelle zwei Schritten. Zuerst werden mit Hilfe eines Plane-Sweep-
mit solchen Einschränkungen sind Landbedeckungsdaten [6]. Verfahrens [1] alle Paare sich schneidender Linien bestimmt.
Diese bestehen aus einer schnittfreien und lückenlosen Men- Anschließend wird jede Linie an allen Schnittpunkten unter-
ge von Flächenobjekten, denen als Objektart jeweils eine teilt, so dass diese im Ergebnis durch mehrere Linien darge-
Landbedeckungsklasse (z.B. Nadelwald) zugeordnet ist. stellt wird, die sich mit anderen Linien nur noch an den End-
Repräsentationsmodelle mit linien- oder flächenhaften Geo- punkten überschneiden. Liegen dabei zwei Linien auf einem
metrien, die nicht schnittfrei sind, werden ein wenig abwer- längeren Abschnitt übereinander, wird für diesen Abschnitt
tend auch als Spaghetti-Datenmodelle bezeichnet [4]. Wäh- nur eine einzelne Linie ins Ergebnis übernommen.
rend sie für die Herstellung von Karten gut geeignet sind, Im Folgenden stellen wir für die Liniensegmentierung drei
bevorzugt man für raumbezogene Analysen sogenannte to- Strategien zur Partitionierung und Rekomposition aus dem
pologische Datenmodelle (TDM). Die grundlegende Struktur in Abschnitt 3 beschriebenen Partitionierungsdienst vor. Es
eines topologischen Datenmodells ist in Abbildung 4 darge- sei angemerkt, dass die für diese Strategien angebotenen Da-
stellt. Knoten bilden punktförmige Objekte in einem TDM tenbankprozeduren in der Anwendbarkeit nicht auf dieses
eine Problem eingeschränkt sind, sondern sich auch für viele
weitere Geoprogramme einsetzen lassen. Beispielsweise wur-
de Variante 1 bereits in [6] erfolgreich für die Generalisierung
von Flächendaten angewendet.
4.1 Clipping & Vereinigung
Wir wählen in dieser Variante für eine Partition alle Ob-
jekte aus, deren Geometrien sich mit dem Partitionspolygon
überschneiden. Zusätzlich schneiden wir bei Objekten am
Rand der Partition den Teil der Geometrie ab, der über das
Partitionspolygon herausragt. Folglich verbleibt nur der in-
nerhalb des Partitionspolygons liegende Anteil als geometri-
sche Repräsentation des Objekts in der Partition. Dies wird
allgemein auch als Clipping bezeichnet. Durch diese Art von
Abb. 4: Datenstruktur eines TDMs Aufteilung kann ein Linienobjekt ggf. in mehreren Partitio-
nen auftreten, allerdings jeweils mit einem unterschiedlichen
ab und können außerdem die Endpunkte von Kanten dar- Teil seiner Geometrie, weshalb wir die Partitionierung als
stellen. Kanten wiederum repräsentieren linienhafte Objek- disjunkt bezeichnen können. Bei der Liniensegmentierung
te und bilden die Ränder von Maschen. Und solche Ma- für eine Partition werden alle Schnitte von Objekten gefun-
schen entsprechen Teilen von flächenhaften Objekten. Die den, die innerhalb des Partitionspolygons liegen, und die
drei Mengen verschiedenartiger TDM-Elemente sind jeweils Geometrien entsprechend aufgeteilt.
schnittfrei, allerdings können ein Knoten oder eine Kante in Betrachtet man die Ergebnisse der Liniensegmentierung
einer Masche enthalten sein. Ein geographisches Objekt ist für die einzelnen Partitionen gemeinsam, fällt auf, dass ne-
durch die TDM-Elemente repräsentiert, durch deren Aggre- ben den korrekten Unterteilungen an den Linienschnittpunk-
gation man die Geometrie des Objekts rekonstruieren kann. ten zusätzlich Unterteilungen an den Schnittpunkten mit
Dabei kann dasselbe Element (z.B. eine Kante) zu mehre- den Rändern der Partitionen auftreten, was auf das Clip-
ren Objekten gehören und repräsentiert in diesem Fall einen ping zurückzuführen ist. Man betrachte z.B. die Situation
gemeinsamen Bestandteil der Geometrien der Objekte, der in Abbildung 5, in der aus drei Linienobjekten a, b und c
c1 c1
b1 b1
a2 a4 a2 a4
a1 a3 a1 a3
b2 c2 b2 c2
Abb. 5: Überflüssige Segmentierung Abb. 6: Überlappende Linien
insgesamt acht segmentierte Linien erzeugt wurden. Bei der weder bereits im Ergebnis enthalten oder werden beim Re-
Unterteilung zwischen a2 und a3 liegt allerdings kein echter komponieren einer der nächsten Partitionen eingefügt. Für
Schnitt vor. Da derartige Situationen ohne Partitionierung Situationen wie in Abbildung 6 bestimmen wir für die sich
nicht auftreten würden, liegen hier Rekompositionskonflik- überlappenden Linien den gemeinsamen Teil durch eine geo-
te vor und müssen durch eine geeignete Operation bereinigt metrische Durchschnittsoperation. Z.B. fügen wir anstelle
werden. Dazu bestimmen wir, welche Linien aus dem bereits der zu langen Linien a2 und a3 nur deren Durchschnitt ins
zusammengesetzten Ergebnis welche anderen Linien aus der Gesamtergebnis ein.
aktuellen Partition an der Partitionsgrenze berühren und fü-
gen diese durch eine Vereinigung zu einer Linie zusammen. 4.3 Objektüberschneidung & Duplikate
Wir müssen allerdings auch berücksichtigen, dass ein Li- Im Vergleich zur vorigen Variante können wir die Elimi-
nienobjekt aus dem Ausgangsdatensatz mehrmals den Rand nierung der Duplikate bei der Rekomposition weiter verein-
der Partition schneiden kann, weshalb wir ggf. auch Grup- fachen, wenn wir bei der Partitionierung noch mehr Red-
pen von mehr als zwei Linien zu einem Objekt vereinigen undanz hinzufügen. Wir bezeichnen dazu die Linienobjekte,
müssen. Ein weiterer Sonderfall liegt vor, wenn sich zwei die das Polygon der Partition p schneiden, als p-Objekte.
Linien aus dem Ausgangsdatensatz genau auf dem Rand Um alle p-Objekte bei der Berechnung für diese Partition
eines Partitionspolygons überschneiden, weil es sich dann korrekt zu segmentieren, müssen wir bei der Partitionierung
bei dem nach obiger Vorschrift ermittelten Berührungspunkt noch Linien von außerhalb der Partition hinzunehmen, die
um einen echten Schnittpunkt handelt und somit keine Ver- sich mit einem p-Objekt überschneiden.
einigung stattfinden darf. Wir können diese Situationen da- Dadurch, dass bei der Partitionierung mehr Objekte re-
durch erkennen, dass sich zwei segmentierte Linien aus der- dundant für mehrere Partitionen ausgewählt werden, ent-
selben Partition an einem solchen Punkt berühren. stehen auch mehr Duplikate, die bei der Rekomposition ent-
fernt werden müssen (siehe Abbildung 7). Die meisten dieser
4.2 Partitionsüberschneidung & Durchschnitt Duplikate werden wir wieder los, indem wir (wie bei Variante
Wie in der ersten Variante wählen wir alle Objekte aus, die 2) Linien außerhalb des Partitionspolygons verwerfen (z.B.
das Partitionspolygon schneiden, verzichten aber auf Clip- a′1 /a′4 ). Bei allen Linien im Ergebnis einer Partition, die den
ping. Die Intention dabei ist es, aufwändige Berechnungen Rand des Partitionspolygons schneiden, können allerdings in
zum Abschneiden und Vereinigen der Geometrien einzuspa- dieser Variante nur echt übereinstimmende Duplikate auftre-
ren. Dafür nehmen wir etwas Redundanz in Kauf, denn Lini- ten, denn diese Linien wurden vollständig segmentiert. An-
en aus dem Ausgangsdatensatz, die über den Rand der Par- statt Durchschnitte zu berechnen, reicht es somit aus, von
tition hinausragen, werden in mehreren Partitionen mit ih- den am Rand der Partition auftretenden Duplikaten (hier
rer vollständigen Geometrie repräsentiert, so dass eine nicht a2 /a3 ) jeweils ein Objekt ins Ergebnis zu übernehmen.
disjunkte Partitionierung vorliegt. Schnitte zwischen solchen
Objekten werden demnach bei der Segmentierung mehrfach
in unterschiedlichen Partitionen berechnet.
Beim Rekomponieren einer Partition müssen Duplikate c1
c'1 a'4
b1
aus den Ergebnissen entfernt werden, da die aus den mehr- b'1 a2 a4
fach repräsentierten Objekten gebildeten Linien auch mehr- a1 a3
fach in den Ergebnissen auftreten. Allerdings stimmen diese a'1 c'2 c2
Duplikate in Bezug auf die Segmentierung nicht zwingend b2
b'2
überein, denn der Schnitt einer über den Rand der Partiti-
on hinausragenden Linie mit einer Linie, die komplett außer-
halb der Partition liegt, wird bei der Berechnung in dieser
Partition nicht gefunden. Man betrachte z.B. die Situation Abb. 7: Doppelte Linien
in Abbildung 6. Während im Ergebnis der linken Partition
(cyan) die Linie a am Schnittpunkt mit b in a1 und a2 unter-
teilt wurde, fehlt die Unterteilung am Schnittpunkt mit c.
Für das Ergebnis der rechten Partition (magenta) hingegen 5. ERGEBNISSE
ist die Situation genau umgekehrt. Um die Anwendbarkeit der in Abschnitt 4 vorgestellten
Um Duplikate zu entfernen, verwerfen wir beim Rekom- Partitionierungs- und Rekompositionsoperationen zu demon-
ponieren einer Partition zunächst alle Linien, die komplett strieren und die Varianten miteinander zu vergleichen, füh-
außerhalb des Partitionspolygons liegen, denn diese sind ent- ren wir Tests mit einem ca. 7,2GB großen kommerziell pro-
duzierten Datensatz durch, der das gesamte Bundesland Hes- kale Algorithmen gelöst werden können, so dass die benötig-
sen umfasst. Diese Daten enthalten Informationen über Stra- te Redundanz bei der Partitionierung nicht zu groß wird.
ßen und weitere für den Kraftfahrzeugverkehr relevante geo- Während für die in diesem Beitrag vorgestellten Expe-
graphische Objekte in Form von Liniengeometrien, die für rimente die Größe der Partitionen fest vorgegeben wurde,
die kartographische Darstellung optimiert und insbesonde- ist es für einen Anwender des Partitionierungsdienstes wün-
re nicht schnittfrei sind. Partitionierung und Rekomposition schenswert, stattdessen die Größe des verfügbaren Speichers
sind in einer Datenbank (Oracle 11g) mit räumlicher Er- angeben zu können, für die der Dienst dann ein geeignetes
weiterung (Oracle Spatial) implementiert. Zur Segmentie- Partitionierungsschema berechnet. Daher arbeiten wir dar-
rung verwenden wir ein Programm aus einer Java-Bibliothek an, Modelle aus der Literatur zum Schätzen der Partitions-
für geometrische Berechnungen (JTS Topology Suite), das größe für räumliche Verbunde zu verallgemeinern, um diese
durch zahlreiche Optimierungen auf Kosten eines hohen Spei- auch auf andere Geoprogramme anwenden zu können. Da-
cherverbrauchs sehr effizient arbeitet. bei muss auch berücksichtigt werden, dass reale geographi-
Wir führen für diesen Datensatz mit jeder der drei Va- sche Daten nicht gleichmäßig verteilt sind, und somit auch
rianten eine Segmentierung durch, wobei wir ein Partitio- die Partitionsgröße innerhalb eines Partitionierungsschemas
nierungsschema aus 129 Quadraten mit jeweils 25km Kan- abhängig von der Datendichte variieren sollte.
tenlänge verwenden. Wir messen und summieren dabei je- Um das Spektrum von möglichen Anwendungen für den
weils separat die Laufzeiten, die bei der Partitionierung, Seg- Partitionierungsdienst zu vergrößern, muss dieser um weite-
mentierung und Rekomposition für alle Partitionen benötigt re Operationen und insbesondere weitere Repräsentations-
werden. Diese Laufzeiten sind in Abbildung 8 dargestellt. modelle erweitert werden. Außerdem werden wir genauer
Die Laufzeit für die Segmentierung ist erwartungsgemäß in untersuchen, wie sich dieser Dienst möglichst gewinnbrin-
gend für die Fortführung von abgeleiteten Datensätzen ein-
setzen lässt. Dieser Ansatz basiert auf der Idee, bei Updates
für Geobasisdaten zunächst möglichst kleine, aber räumlich
zusammenhängende Gebiete zu identifizieren, in denen Än-
derungen stattgefunden haben. Für die Aktualisierung von
abgeleiteten Datensätzen müssen dann unter Verwendung
von Partitionierung und Rekomposition nur diese Gebiete
an Stelle des kompletten Datensatzes neu berechnet werden.
7. DANKSAGUNG
Diese Arbeit wurde vom Bundesamt für Kartographie und
Geodäsie im Rahmen des Projekts Wissensbasierter Photo-
grammetrisch-Kartographischer Arbeitsplatz (WiPKA) ge-
fördert.
Abb. 8: Laufzeiten (in Sek.) der Prozessphasen
8. LITERATUR
[1] Berg, M. de ; Cheong, O. ; Kreveld, M. van ;
Overmars, M. : Computational Geometry: Algorithms
der ersten Variante am geringsten und steigt durch das Hin-
and Applications. 3.Aufl. Springer-Verlag, 2008
zufügen von mehr Redundanz in Variante 2 und 3 jeweils
leicht an. Am meisten Zeit benötigt in allen Varianten die [2] Dittrich, J.-P. ; Seeger, B. : Data Redundancy and
Rekomposition. Während diese in Variante 3 die geringste Duplicate Detection in Spatial Join Processing. In:
Laufzeit benötigt, ist dabei jedoch eine vergleichsweise auf- Proc. ICDE 2000, San Diego, S. 535–546
wändige Partitionierung nötig. Die beste Gesamtlaufzeit hat [3] Güting, R. H. ; Schilling, W. : A Practical
somit Variante 2, bei der die Partitionierung am schnellsten Divide-and-Conquer Algorithm for the Rectangle
geht und die Zeiten für Segmentierung und Rekomposition Intersection Problem. In: Information Sciences 42
jeweils in der Mitte liegen. (1987), Nr. 2, S. 95–112
[4] Hake, G. ; Grünreich, D. ; Meng, L. : Kartographie.
6. FAZIT 8.Aufl. Walter de Gruyter & Co., 2002
[5] Patel, J. M. ; DeWitt, D. J.: Partition Based
Der in diesem Beitrag vorgestellte Partitionierungsdienst
Spatial-Merge Join. In: Proc. SIGMOD 1996, Montreal,
für geographische Daten in räumlichen Datenbanken besteht
S. 259–270
im Wesentlichen aus einer Sammlung von flexibel anwendba-
ren Partitionierungs- und Rekompositionsoperationen. Die- [6] Thiemann, F. ; Warneke, H. ; Sester, M. ; Lipeck,
se erlauben es, Geoprogramme mit sehr geringem Entwick- U. : A Scalable Approach for Generalization of Land
lungsaufwand fit für die Bearbeitung großer Datenmengen Cover Data. In: Proc. 14th AGILE Intl.Conf. on Geo-
zu machen. Dabei bleibt die Freiheit der Wahl einer Pro- graphic Information Systems. Utrecht, 2011, S. 399–420
grammiersprache und von Software-Bibliotheken sowie die [7] Warneke, H. ; Schäfers, M. ; Lipeck, U. ; Bobrich,
gute Wartbarkeit der Geoprogramme erhalten, da Zugriffe J. : Matching-Based Map Generalization by
auf extern gespeicherte Daten nur während der Partitionie- Transferring Geometric Representations. In: Proc.
rung und Rekomposition erfolgen müssen. Neben dem an Geoinformatik 2011, Münster, S. 71–77
dieser Stelle vorgestellten Anwendungsbeispiel eignet sich [8] Zhou, X. ; Abel, D. J. ; Truffet, D. : Data
diese Vorgehensweise für eine Vielzahl weiterer geographi- Partitioning for Parallel Spatial Join Processing. In:
scher Problemstellungen, sofern diese durch hinreichend lo- GeoInformatica 2 (1998), Nr. 2, S. 175–204