Z-order curve

The Z- curve ( Lebesgue curve ) is a space-filling curve, which is used in computer science for multidimensional data structures. The Z value of a point in space is simply by bitwise interleaving the coordinate values ​​calculated (bit interleaving ). As space-filling curves represent the data to one dimension, each one-dimensional data structure can be used, such as a simple table that a skip - list, a binary search tree, a B- tree or a B tree. In the latter case, it is named after Rudolf Bayer UB- Tree (Universal B- Tree ).

The Z- curve is popular because of its good neighborhood preservation and the simple predictability of Z values ​​. In the Hilbert curve, the neighborhood preservation is better, but the calculations are more complicated.

Omitting low significant bits one can use the Z- values ​​for hash tables in which neighborhood searches are possible.

This figure shows the Z values ​​for the two-dimensional case with the coordinates x = 0 to 7, y = 0 to 7; one follows the values ​​that are obtained recursively a Z-shaped curve.

Despite the good neighborhood preservation, an algorithm is required for multidimensional range search in order, starting from one encountered in the data structure outside the search area point to determine the next Z- value whose coordinates lie in the search area.

In this example, the search range (x = 2 .3, y = 2 .6 ) indicated by the dotted rectangle. The highest Z value is (MAX) is 45 Suppose that in the course of the search, the value F = 19 is encountered, in search of increasing values ​​. Then you would have the interval between F and Max search ( shaded area ). To speed up the search, we calculate the next Z- value in the search area, hereinafter referred BIGMIN (36 in the example). Then only the interval between BIGMIN and MAX must be searched (bold subscribed values ​​) characterized the majority of the shaded region is skipped. The search for falling values ​​is analogous with LITMAX, the largest Z value in the search area, which is less than F. The problem and its solution was first described in. The solution is also used in the UB- tree ( " GetNextZ -address ").

By hierarchically ( according to the used data structure) using the method, if appropriate after both rising and falling Z values ​​, one obtains a highly efficient multi-dimensional range search; this is useful in both the commercial and technical applications, eg as a basic function for (Next ) proximity searches.

BIGMIN source code for Z- curve and Hilbert curve can be found in.