Z-order (curve)
From Wikipedia, the free encyclopedia
z-order (aka Morton-order) 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 bitwise interleaving its coordinate values. 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.
This figure shows the z-values for the two dimensional case with coordinates x=0..7, y=0..7; Interleaving the binary coordinate values yields z-values as shown. Following the values in order is the recursively Z-shaped curve.
Although well locality preserving, for efficient range searches an algorithm is necessary for calculating, from a point encountered in the data structure, the next Z-value which is in the multidimensional search range.
In this example, the range being queried (x=2..3, y=2..6) is indicated by the dotted rectangle. Its highest Z-value (MAX) is 45. Say the value F=19 is encountered when searching a data structure in increasing Z-value direction, so we would have to search in the interval between F and MAX (hatched area). To speed up the search, we calculate the next Z-value which is in the search range, called BIGMIN (36 in the example) and only search in the interval between BIGMIN and MAX (bold values), thus skipping most of the hatched area. Searching in decreasing direction is analogous with LITMAX which is the highest Z-value in the query range lower than F. The problem has first been addressed and its solution shown in [1]. The solution is also used in UB-trees ("GetNextZ-address").
Applying the method hierarchically (according to the data structure at hand), optionally in both increasing and decreasing direction, yields highly efficient multidimensional range search which is important in both commercial and technical applications, e.g. as a procedure underlying nearest neighbour searches.
As an alternative, the Hilbert curve has been suggested as it has a better order preserving behaviour, but here the calculations are much more complicated, leading to significant processor overhead.
BIGMIN source code for both Z-curve and Hilbert-curve can be found in [2]
[edit] References
- ^ [1] H. Tropf, H. Herzog: Multidimensional Range Search in Dynamically Balanced Trees, Angewandte Informatik, 2/1981, pp 71-77.
- ^ H. Tropf: US patent application 2004/0177065
