HZ order indexing

HZ ordering consists of two parts: a hierarchical decomposition imposed on an underlying ordering. The underlying ordering that used by IDX is a generalization of the Z-order curve, due to its simplicity for index computation. The hierarchical decomposition used by IDX is a binary tree in which the elements of level i have the last i bits all equal to 0.

Z-order curve

The Z-order is a function that maps multidimensional data to one dimension by interleaving the binary representations of each data point's coordinate values. A good description of the Z-order curve is here.

Bit string and kd-tree

In Z-order indexing, the bits in binary representations of each coordinate are interleaved in a regular way. To generalize this, IDX uses a bit string to specifies the way the bits are interleaved. Assuming the domain is a 8x16x32 grid in 3D, the representations of indices in each dimension is as follows:

X: xxx (3 bits) Y: yyyy (4 bits) Z: zzzzz (5 bits)

The Z-order index is computed as xyzxyzxyzyzz. The more conventional row-order index is computed as xxxyyyyzzzz. In IDX, if we use the bit string V011201220122, the HZ index is xyyzxyzzxyzz.

Hierarchical ordering