| p:abstract
| - Z-order, or Morton-order, first proposed in 1966 by G. M. Morton, is a space-filling curve which is often used in computer science: Due to its good locality-preserving behaviour it is used in data structures for mapping multidimensional data to one dimension. The z-value of a point in multidimensions is simply calculated by interleaving the binary representations of its coordinate values. Once the data are sorted into this ordering, any one-dimensional data structure can be used such as binary search trees, B-trees, skip lists or (with low significant bits truncated) hash tables. The resulting ordering can equivalently be described as the order would get from a depth-first traversal of a quadtree; because of its close connection with quadtrees, the Z-ordering can be used to efficiently construct quadtrees and related higher dimensional data structures. (en)
- Z-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 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. 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. In diesem Beispiel ist der Suchbereich mit dem gepunkteten Rechteck angezeigt. Der höchste Z-Wert darin 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 . Um die Suche zu beschleunigen, berechnen wir den nächsten Z-Wert im Suchbereich, im folgenden BIGMIN genannt . Dann muss nur das Intervall zwischen BIGMIN and MAX durchsucht werden, 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 . Die Lösung wird ebenso verwendet im UB-Baum . Indem man die Methode hierarchisch 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 . (de)
|
![[RDF Data]](http://dbpedia.org/statics/sw-cube.png)
