Z-Kurve

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Abb. 1: Vier Iterationen der Z-Kurve.

Die Z-Kurve (Lebesgue-Kurve, engl. Z-order curve) ist eine Abbildung, die Punkte aus dem mehrdimensionalen Raum in eine lineare Ordnung, die Z-Ordnung[1] oder Morton-Ordnung,[2] bringt, eine Ordnung mit nachbarschaftserhaltenden Eigenschaften. Der Z-Wert eines Raumpunktes wird durch bitweises Verschränken der binären Koordinatenwerte berechnet.[3]

Mit ihrer Hilfe lassen sich (effiziente) Verfahren, die auf einer linearen Ordnung beruhen, ins Mehrdimensionale übertragen. Dazu gehört Binäres Suchen, Binärer Suchbaum, Skip-Liste, B-Baum, oder ein B+-Baum. Im letzteren Fall wird er nach Rudolf Bayer UB-Baum (Universal B-Tree) genannt.[4]

Beim direkten Zugriff steht die Morton-Ordnung in Konkurrenz zu einem Zugriff, bei dem die linearen Ordnungen der Dimensionen in unterschiedlicher Rangigkeit zu einer lexikographischen Ordnung hintereinander geschaltet sind – im internen Speicher über ein mehrfach indiziertes Feld resp. im externen Speicher per wahlfreien Zugriff (Random Access). Wenn sich dies gut organisieren lässt, schneidet sie etwas schlechter ab. Sie ist aber überlegen, wenn sich an einen solchen Zugriff eine sequentielle Suche anschließt, bei der Nachbarschaftsbeziehungen vorteilhaft ausgenutzt werden können. 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 Rechnungen komplizierter.

Dieser Artikel beschäftigt sich vorwiegend mit dem zweidimensionalen Fall.

Zahlentheorie[Bearbeiten | Quelltext bearbeiten]

Abb. 2: Z-Kurve (grau) der dritten Iteration.
x-Bits blau, y-Bits rot

Die nebenstehende Abbildung 2 zeigt die Z-Werte im zweidimensionalen Fall für ganzzahlige Koordinaten . Das bitweise Verschränken der - und -Werte (auch bitweises Verzahnen oder Binärbruchpressung genannt) ergibt die binären -Werte. Verbindet man diese in ihrer aufsteigenden numerischen Reihenfolge, dann entsteht eine Kurve (Polygonzug), die Z-Kurve genannt wird.[5] Die zugrunde liegende Abbildung sei in ihrer -ten Iteration mit

bezeichnet. Sie lässt sich leicht auf höhere Dimensionen erweitern und ist umkehrbar eindeutig (bijektiv).[6]

In den binären Darstellungen der Z-Werte für gibt es 1-Bits höchstens an Binärstellen mit gerader Nummer. Im System zur Basis 4 bestehen diese Zahlen also nur aus Ziffern 0 und 1.[7] Diese Zahlen heißen Z-Werte im engeren Sinn oder Moser-de Bruijn-Zahlen. Sie machen die Folge A000695 in OEIS aus.

Fürs Folgende sei diese Folge spezifiziert als

,

wobei der ersten Komponente der Index 0 gegeben wird. Summen und Differenzen zweier -Komponenten lassen sich bilden durch die bitweisen Operationen

und
falls ,

mit und mit den Operatoren für bitweises logisches UND und für bitweises logisches ODER, jeweils angewendet auf die in Bitketten aufgelösten Operanden.

Eine Formel zum Erzeugen des Folgeelements aus dem Vorgänger ist

.[8]

Anwendungen in der Informatik[Bearbeiten | Quelltext bearbeiten]

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

Abb. 3: Rechteckiger Suchbereich

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.

Im Beispiel der nebenstehenden Abbildung ist der Suchbereich (x=2..3, y=2..6), ein 2D-Intervall, als gestricheltes Rechteck angezeigt. Der höchste Z-Wert darin ist MAX=45. Angenommen, im Laufe der Suche wird der Wert F=19 angetroffen, bei Suche nach steigenden Werten. Das 1D-Intervall zwischen F und MAX (schraffiertes Gebiet) ist Obermenge des noch zu durchsuchenden Teils des Rechtecks. 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 und 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 im Jahr 1981 von Tropf und Herzog beschrieben.[9] 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 die Z-Kurve und die Hilbert-Kurve findet man in der Patentschrift von Tropf.[10] [8] [11]

Die hierarchische Anwendung dieser Methode, angepasst an die zugrundeliegende Datenstruktur und sowohl aufsteigende wie absteigende Suchrichtung unterstützend, ermöglicht eine hocheffiziente Bereichssuche in kommerziellen wie in technischen Anwendungen. Die Morton-Ordnung ist eine der wenigen mehrdimensionalen Zugriffsmethoden, die ihren Weg in kommerzielle Datenbanksysteme gefunden haben (Transbase[4]).

Analysis[Bearbeiten | Quelltext bearbeiten]

Binärbruchverschränkung[Bearbeiten | Quelltext bearbeiten]

Die durch unendliche Iteration der obigen Vorschrift „definierte“ und auf das Einheitsintervall normalisierte Abbildung

mit Ziffern ist zunächst nicht wohldefiniert, weil es zu einem gekürzten Bruch mit Zweierpotenz im Nenner, also zu einem Element , zwei Möglichkeiten der Darstellung gibt. Beispielsweise hat der Bruch die Darstellung mit einem 02-Ende

und die mit einem 12-Ende

.[12]

Diese Wahlmöglichkeit (Gleichheit) ist bei endlichem nicht gegeben, im Limes aber sehr wohl, wo sie die für eine Funktion erforderliche Rechtseindeutigkeit von zerstört, da sie sich auf das Ergebnis der Verschränkung auswirkt. Rechtseindeutigkeit lässt sich aber wiederherstellen, beispielsweise durch eine der folgenden Vorschriften:

Vorschrift A:  Die Binärdarstellung eines Bruchs hat immer ein 02-Ende. Das entspricht der üblichen abbrechenden Darstellung und einer Annäherung an von oben her.
Diese Variante von sei mit bezeichnet.
Vorschrift B:  Die Binärdarstellung von 0 ist 02. Die Binärdarstellung eines Bruchs hat immer ein 12-Ende. (Ist , dann ist die Binärdarstellung zu nehmen.) Das entspricht einer Annäherung an von unten her, also einer linksseitigen Grenzwertbildung bei jeder Funktion, bei der es auf die Binärdarstellung ankommt, beispielsweise einem Limes .[13]
Diese Variante von sei mit bezeichnet.

Durch jede der beiden Vorschriften wird wohldefiniert und ist auch injektiv.

ist aber nicht surjektiv. Denn bei beiden Vorschriften gibt es zu kein Urbild, da die -Koordinate zwingend ein 02-Ende und die -Koordinate zwingend ein 12-Ende haben müsste (resp. umgekehrt bei .) Das Bild des Einheitsquadrates unter ist

bei Vorschrift A resp.
bei Vorschrift B.

Ihm fehlt in beiden Fällen zum Einheitsintervall eine abzählbare dichte Teilmenge. Somit ist es nicht kompakt. (Gleichwohl ist die abgeschlossene Hülle des Bildes .)

ist auch nicht stetig, da an den Punkten eine infinitesimale Änderung des Arguments eine endliche Änderung des Funktionswerts bewirkt. Das kann man schon in der obigen Abbildung 2 erkennen, beispielsweise am Einserschritt der -Koordinate von zu oder am Einserschritt der -Koordinate von Punkt zu Punkt , wo die Positionsnummer in der Z-Kurve um mehr als ein Drittel (32−10=22 > 64/3) resp. um mehr als ein Sechstel (16−5=11 > 64/6) ihrer Gesamtlänge (64) zunimmt.

Genaue Überlegung        

Enthält die Binärdarstellung einer Zahl keine 1, dann handelt es sich um die 0, und es gibt keine Wahlmöglichkeit, diese mit einem 12-Ende so darzustellen, dass derselbe Zahlenwert 0 herauskommt.

Für die Untersuchung der Stetigkeit an einem Punkt kann man die Differenzen zweier einseitiger Grenzwerte heranziehen. Denn genau dann, wenn diese alle 0 sind, ist die Funktion am Punkt stetig. Ist weder noch ein abbrechender Binärbruch, dann stimmen die einseitigen Grenzwerte von überein[13] und ist stetig bei . Ist aber beispielsweise ein abbrechender Binärbruch , dann entspricht der linksseitige Grenzwert einem 12-Ende von , während der rechtsseitige Grenzwert einem 02-Ende von entspricht.[14]

Zunächst werde eine Binärbruchverschränkung für untersucht mit nicht abbrechendem und abbrechendem mit und .

mit 02-Ende
mit 12-Ende
Überträge                
Differenz

Die erste Zeile enthält die verschränkten Binärziffern von , wenn mit 02-Ende dargestellt wird, die zweite für dasselbe dargestellt mit 12-Ende, die dritte enthält die Überträge der binären Subtraktion und die vierte Zeile enthält die Sprunghöhe, d. i. die Differenz »abbrechendes « der ersten beiden Zeilen im Limes, also

.

Für mit abbrechendem bei und und mit nicht abbrechendem ist analog

mit 02-Ende
mit 12-Ende
Überträge            
Differenz

Die Differenz »abbrechendes « ist im Limes

.

Ist , dann addieren sich die Sprunghöhen.

Raumfüllend[Bearbeiten | Quelltext bearbeiten]

Die „Umkehrfunktion“

mit ist – wie das obige aus demselben Grund der fehlenden Rechtseindeutigkeit infolge mehrdeutiger binärer Darstellbarkeit – zunächst nicht wohldefiniert. Wie dort lässt sich die Rechtseindeutigkeit durch die Vorschrift herstellen, dass ein Bruch entweder immer nur mit 02-Ende (Vorschrift A) oder immer nur mit 12-Ende (Vorschrift B) zu expandieren ist. Je nachdem sei die Variante von mit oder mit bezeichnet. Durch jede der beiden Vorschriften wird wohldefiniert. Sie bildet das Einheitsintervall surjektiv („raumfüllend“) auf das Einheitsquadrat ab.

Sie ist aber nicht injektiv, denn die Punkte aus haben mehrere Urbilder. Beispielsweise hat der Punkt sowohl

wegen als auch
wegen

zum -Urbild. Die Umkehrung davon entspricht mit genau den zwei einseitigen Grenzwerten

und
.

Etwas anders liegt der Fall bei den im vorigen Abschnitt Binärbruchverschränkung erwähnten Punkten und , die weder Bildpunkte von noch von sind. Unter ist

und
,

wogegen die einseitigen Grenzwerte von am Punkt

und

sind.

ist nicht stetig[15] an einem Punkt , weil linksseitiger Grenzwert ( am 12-Ende) und rechtsseitiger ( am 02-Ende) sich im Ergebnis unterscheiden[14] (s. Tabelle mit Beispielen).

Die Summe aller „Sprungweiten“ der Unstetigkeitsstellen (s. Tabelle) wächst exponentiell mit der Zahl der Iterationen, da pro Iteration (s. Abbildung 1) die Weite der Sprünge zwar mit dem Faktor 2 abnimmt, die Anzahl der Sprünge jedoch mit dem Faktor 4 zunimmt.

Tabelle mit Beispielen        
Erläuterung zu den Spalten der Tabelle
  1. Der Exponent korreliert mit der Iterationsnummer () der Abbildung 1.
  2. Zu den z-Werten gibt es (mindestens) eine Unstetigkeitsstelle der - oder -Koordinate. Die Spalte enthält den kleinsten zu gehörigen z-Wert, die anderen sind ungerade Vielfache davon und werden nur gezählt (in der Spalte Anzahl). Für die Zwecke der nächsten Spalte sind die x-Bits blau und die y-Bits rot eingefärbt.
  3. ist gleichzeitig der rechtsseitige Grenzwert .
  4. Die nächste Spalte zeigt denselben z-Wert, aber mit dem 12-Ende. Auch hier sind die x-Bits blau und die y-Bits rot eingefärbt.
  5. Entsprechend dieser Einfärbung sind die Bits in der Spalte -Ende in - und -Koordinate aufgeteilt.
  6. bringt den linksseitigen Grenzwert (eine seiner Koordinaten ist , die andere größer).
  7. Richtung gibt an, welche Koordinate sich ändert. Beispielsweise bedeutet ↑, dass sich die -Koordinate an dieser Stelle bei infinitesimal wachsendem ändert, und zwar fallend und in den Abbildungen 1 und 2 nach oben.
  8. Weite enthält die euklidische Distanz der beiden Grenzwerte.
  9. Anzahl enthält die Anzahl von Unstetigkeitsstellen (im Einheitsquadrat) mit dieser Richtung und Weite.
  10. Der Beitrag zur Gesamtsumme der Sprungweiten ist das Produkt von Weite mal Anzahl.

 

-Ende
 
-Ende Rich-
tung
Wei-
te
An-
zahl
Bei-
trag
1 1   1
2 2 +1
3 4 +2
4 8 +2
5 16 +4
Tab. 1: Die Sprungweiten von in Abhängigkeit vom Exponenten

Weitere Werte:

Weitere Limites gegenübergestellt für

Wegen der Unstetigkeit von ist die Bildmenge von keine Kurve. Da sie aber in der Ebene liegt, also zweidimensional ist, und bei wachsendem Argument an einer Unstetigkeitsstelle immer nur in der - oder der -Koordinate springt, lassen sich die beiden Ränder (linksseitiger und rechtsseitiger Grenzwert) der Unstetigkeitsstelle durch eine Parallele zur Achse der springenden Koordinate verbinden, wie es die Abbildung 1 nahelegt (und wie es in der Abbildung 4 andeutungsweise ausgeführt ist). Dadurch entsteht eine stetige Abbildung , deren Bild Z-Kurve genannt wird. Die Stetigkeit impliziert, dass linksseitige und rechtsseitige Grenzwerte gleich sind; mit der Folge, dass Rechtseindeutigkeit auch ohne Entscheidung für Vorschrift A oder Vorschrift B besteht. ist stetig und surjektiv, aber nicht injektiv.[16] Da die endlichen Iterationen gleichwohl injektiv und damit selbst-ausweichend sind, gehört die Z-Kurve zu den FASS-Kurven, die ihrerseits eine echte Teilmenge der raumfüllenden Kurven sind.[17]

Explizite Formulierung        
Abb. 4: Z-Kurve der dritten Iteration.
Bei drei beispielhaften Sprüngen sind stetig machende Verbindungsstrecken hinzugefügt, die im Limes achsenparallel die Parallele überqueren.

Das Folgende gibt eine explizite Formel für die stetige Z-Funktion.

Um die Verbindungsstrecken in Definitionsmenge (und Bildmenge) unterzubringen, wird das Argument ternär, also zur Basis 3 und mit den Ziffern 0, 1, 2 geschrieben. Die Binärbruchverschränkung findet nur bei Ziffern 0 und 1 statt. Dem ersten Auftreten der Ziffer 2 wird die Bedeutung gegeben, dass die als ternäre Zahl aufgefassten nachfolgenden Ziffern die Verbindungsstrecke zwischen dem anliegenden linksseitigen und rechtsseitigen Grenzwert geradlinig parametrisieren.

Die die Unstetigkeitsstelle der ersten Iteration verbindende Strecke läuft vom Punkt zum Punkt und hat die Länge 1. Sie findet sich in der untenstehenden Tabelle in den drei Zeilen mit (s. auch Abbildung 4). Um die Fläche des Einheitsquadrats zu füllen, kann man einfacherweise vom Intervall ausgehen, denn es erübrigt sich, für die erste Ternärziffer eine 2 zuzulassen.

Sei also und mit und eine ternäre Darstellung. Ferner sei

der kleinste Index mit einer Ziffer 2 (folglich ) und

    (nur benötigt, wenn ).

Außerdem sei

(nur Ziffern mit geradem Index ) und
(nur Ziffern mit ungeradem Index )

und schließlich

und
    (nur benötigt, wenn ).

Dann ist die Funktion

 

die stetig ergänzte Iteration der Nummer der Kurve in den Abbildungen 1 und 2, die Z-Kurve im engeren Sinn. Diese ist surjektiv, aber nicht injektiv.

Einige Beispiele:


 
Rich-
tung

 
2
2
2
3
3
3
4
4
4
Tab. 2: Bildpunkte von , darunter 3 Verbindungsstrecken mit den Exponenten

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise und Anmerkungen[Bearbeiten | Quelltext bearbeiten]

  1. Volker Gaede, Oliver Guenther: Multidimensional access methods. In: ACM Computing Surveys. 30, Nr. 2, 1998, S. 170–231. doi:10.1145/280277.280279.
  2. G. M. Morton: A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing. In: IBM Ltd. (Hrsg.): Technical Report. , Ottawa, Canada1966.
  3. Streng genommen ist nicht diese Abbildung, sondern allenfalls ihre Umkehrung eine raumfüllende Kurve.
  4. a b Frank Ramsak, Volker Markl, Robert Fenk, Martin Zirkel, Klaus Elhardt, Rudolf Bayer: Integrating the UB-tree into a Database System Kernel Archiviert vom Original am 4. März 2016. i Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe den Link gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/www.mistral.in.tum.de In: Int. Conf. on Very Large Databases (VLDB). 2000, S. 263–272.
  5. In der Literatur ist es Konvention, die -Bits links vor die -Bits zu stellen. Dadurch entsteht die charakteristische Z-Form, wenn (wie in den Abbildungen 1 und 2) nach rechts und nach unten wächst.
  6. Die Injektivität geht bei (genauer: im ) verloren. Die ebenfalls auftretenden Probleme mit der Rechtseindeutigkeit haben dieselbe Ursache (s. u.).
  7. Die Punkte der Cantor-Menge enthalten in ihrer klassischen Darstellung zur Basis 3 nur Ziffern 0 und 2.
  8. a b Jeyarajan Thiyagalingam, Olav Beckmann, Paul H. J. Kelly: Is Morton layout competitive for large two-dimensional arrays yet?. In: Concurrency and Computation: Practice and Experience. 18, Nr. 11, September 2006, S. 1509–1539. doi:10.1002/cpe.v18:11.
  9. H. Tropf, H. Herzog: Multidimensional Range Search in Dynamically Balanced Trees. Angewandte Informatik, 2/1981, pp 71–77.
  10. Patent US7321890: Database and method for organizing data elements. Angemeldet am 18. Februar 2004, veröffentlicht am 22. Januar 2008, Erfinder: Hermann Tropf (verfallen).
  11. http://pubs.doc.ic.ac.uk/Morton-competitive-yet/
  12. Um Undeutlichkeiten oder Verwechslungen mit dem Komma der Notationen für Intervalle oder Koordinatenpaare zu vermeiden, wird im Folgenden als Trennzeichen zu den Stellen mit negativen Exponenten der Punkt verwendet. Wir folgen diesbezüglich M. Bader wie auch in der Platzierung der Basis als Präfix bei diesem Punkt.
  13. a b Für ist
    sowie
    .
  14. a b Diese Begründung für Unstetigkeit gilt völlig unabhängig von der Entscheidung ob Vorschrift A oder Vorschrift B.
  15. Michael Bader: Space-Filling Curves. An Introduction with Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Hrsg.]: Texts in Computational Science and Engineering. Band 9). 1. Auflage. Springer-Verlag, 2013, ISBN 978-3-642-31045-4, ISSN 1611-0994, doi:10.1007/978-3-642-31046-1 (englisch, 278 S.). S. 96.
  16. Stetig und bijektiv ist nur möglich bei gleicher Dimension (Satz von der Invarianz der Dimension).
  17. Es gibt raumfüllende Kurven, die auch im Limes von vorn herein stetig sind, wie die Hilbert-Kurve und die Peano-Kurve. Insofern deutet die hier nachgebesserte Stetigkeit der Z-Kurve ein verbesserungsfähiges Nachbarschaftsverhalten an.

Weblinks[Bearbeiten | Quelltext bearbeiten]