Z-Kurve

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Z-Kurve (Lebesgue-Kurve) ist eine raumfüllende Kurve, die in der Informatik für mehrdimensionale Datenstrukturen verwendet wird. Der Z-Wert eines Raumpunktes wird einfach durch bitweises Verschränken der Koordinatenwerte berechnet (Bit Interleaving). Da raumfüllende Kurven die Daten auf eine Dimension abbilden, kann jede eindimensionale Datenstruktur verwendet werden, wie z. B. eine einfache Tabelle, eine Skip-Liste, ein binärer Suchbaum, ein B-Baum, oder ein B+-Baum. Im letzteren Fall wird er nach Rudolf Bayer UB-Baum (Universal B-Tree) genannt.

Die Z-Kurve ist beliebt aufgrund ihrer guten Nachbarschaftserhaltung und der einfachen Berechenbarkeit der Z-Werte. Bei der Hilbert-Kurve ist die Nachbarschaftserhaltung besser, doch sind die Berechnungen komplizierter.

Unter Weglassung gering signifikanter Bits kann man die Z-Werte für Hashtabellen verwenden, in denen Nachbarschaftssuchen möglich sind.

Z-CURVE.svg

Diese Abbildung zeigt die Z-Werte für den zweidimensionalen Fall mit den Koordinaten x=0..7, y=0..7; folgt man den Werten, so erhält man eine rekursiv Z-förmige Kurve.

Trotz der guten Nachbarschaftserhaltung ist für die mehrdimensionale Bereichssuche ein Algorithmus erforderlich, um, ausgehend von einem in der Datenstruktur außerhalb des Suchbereichs angetroffenen Punkt, den nächsten Z-Wert zu bestimmen, dessen Koordinaten im Suchbereich liegen.

BIGMIN.svg

In diesem Beispiel ist der Suchbereich (x=2..3, y=2..6) mit dem gepunkteten Rechteck angezeigt. Der höchste Z-Wert darin (MAX) ist 45. Angenommen, im Laufe der Suche wird der Wert F=19 angetroffen, bei Suche nach steigenden Werten. Dann müsste man das Intervall zwischen F und Max durchsuchen (schraffiertes Gebiet). Um die Suche zu beschleunigen, berechnen wir den nächsten Z-Wert im Suchbereich, im folgenden BIGMIN genannt (36 im Beispiel). Dann muss nur das Intervall zwischen BIGMIN and MAX durchsucht werden (fett gezeichnete Werte), dadurch wird der Großteil des schraffierten Gebiets übersprungen. Die Suche nach fallenden Werten ist analog dazu, mit LITMAX, dem größten Z-Wert im Suchbereich, der kleiner ist als F. Das Problem und seine Lösung wurde zuerst beschrieben in.[1] Die Lösung wird ebenso verwendet im UB-Baum („GetNextZ-address“).

Indem man die Methode hierarchisch (entsprechend der verwendeten Datenstruktur) einsetzt, ggf. nach sowohl steigenden als auch fallenden Z-Werten, erhält man eine hocheffiziente mehrdimensionale Bereichssuche; dies ist nützlich sowohl in kommerziellen als auch technischen Anwendungen, z. B. als Grundfunktion für (Nächste-) Nachbarschaftssuchen.

BIGMIN Quellcode für Z-Kurve und Hilbert-Kurve findet man in.[2]

Einzelnachweise[Bearbeiten]

  1. http://www.vision-tools.com/h-tropf/multidimensionalrangequery.pdf H. Tropf, H. Herzog: Multidimensional Range Search in Dynamically Balanced Trees, Angewandte Informatik, 2/1981, pp 71–77.
  2. H. Tropf: US Patent 7,321,890