In der bisherigen Anwendung
repräsentierten die Datenpunkte im k-dimensionale Raum
-stellige Attributkombinationen. Wir wollen jetzt
mithilfe der Datenpunkte geometrische Objekte darstellen
und einfache geometrische Anfragen realisieren.
Abbildung 5.14 zeigt eine Ansammlung von Intervallen, die zu verwalten seien. Die Intervalle sollen durch Punkte im mehrdimensionalen Raum dargestellt werden. Wenn alle Intervalle durch ihre Anfangs- und Endpunkte repräsentiert würden, kämen sie auf der Datenfläche nur oberhalb der 45-Grad-Geraden zu liegen.
Abbildung 5.15 präsentiert eine wirtschaftlichere Verteilung, indem jede Gerade durch ihren Mittelpunkt und ihre halbe Länge repräsentiert wird.
Typische Queries an die Intervall-Sammlung lauten:
Abbildung 5.16
zeigt den kegelförmigen Abfragebereich zum
Query-Punkt =5, in dem alle
Intervalle (repräsentiert durch Punkte) liegen,
die den Punkt
enthalten.
Grundlage ist die Überlegung, daß ein Punkt
genau dann im Intervall mit Mitte
und
halber Länge
enhalten ist, wenn gilt:
Abbildung 5.17 zeigt den
kegelförmigen Abfragebereich zu dem Query-Intervall mit
Mittelpunkt =10 und halber Länge
=1, in dem
alle Intervalle (repäsentiert durch Punkte) liegen,
die das Query-Intervall schneiden.
Grundlage ist die Überlegung, daß
ein Intervall mit Mitte
und halber Länge
genau dann
ein Intervall mit Mitte
und halber Länge
schneidet,
wenn gilt:
Abbildung 5.18
zeigt die Vorgehensweise bei der Bestimmung des
nächstgelegenen Nachbarn (englisch: nearest neighbor).
Suche zunächst auf dem Datenblock, der für den Query-Point
zuständig ist, den nächstgelegenen Punkt
.
Bilde eine Range-Query mit Quadrat um den Kreis um
mit Radius
.
Schränke Quadratgröße weiter ein, falls nähere Punkte
gefunden werden.
Die erwähnten Techniken lassen sich auf höherdimensionierte
Geometrie-Objekte wie Rechtecke oder Quader erweitern.
Zum Beispiel bietet
sich zur Verwaltung von orthogonalen Rechtecken in der Ebene folgende
Möglichkeit an:
Ein Rechteck wird repräsentiert als ein Punkt im 4-dimensionalen Raum,
gebildet durch die beiden 2-dimensionalen Punkte für horizontale
bzw. vertikale Lage. Zu einem Query-Rechteck, bestehend aus horizontalem
Intervall und vertikalem Intervall
, lassen sich die schneidenden
Rechtecke finden im Durchschnitt der beiden kegelförmigen
Abfragebereiche zu den Intervallen
und
.