Package org.apache.iceberg.util

Class HilbertByteUtils

java.lang.Object
org.apache.iceberg.util.HilbertByteUtils
public class HilbertByteUtils extends Object
Maps a set of columns (each already converted to fixed-width, lexicographically-ordered unsigned bytes by ZOrderByteUtils) onto a single byte array whose unsigned big-endian lexicographic ordering follows the multi-dimensional Hilbert space-filling curve.

Unlike Z-ordering, the Hilbert transform requires every dimension to contribute the same number of bits, so each column is read to a fixed bitsPerColumn precision.

The transform is the standard "axes to transposed Hilbert index" algorithm from J. Skilling, "Programming the Hilbert curve," AIP Conf. Proc. 707, 381 (2004), https://doi.org/10.1063/1.1751381; the transposed index is then serialized to a scalar with ZOrderByteUtils.interleaveBits(byte[][], int).

  • Method Details

    • hilbertIndex

      public static byte[] hilbertIndex(byte[][] columnsBinary, int bitsPerColumn)
      See hilbertIndex(byte[][], int, ByteBuffer).

    • hilbertIndex

      public static byte[] hilbertIndex(byte[][] columnsBinary, int bitsPerColumn, ByteBuffer reuse)
      Compute the Hilbert index for the given columns.
      Parameters:
      columnsBinary - one ordered-byte array per column; each must be at least bitsPerColumn / 8 bytes long (only the leading bytes are used)
      bitsPerColumn - bits taken from each column; a positive multiple of 8, no greater than 64
      reuse - a buffer with capacity at least numColumns * bitsPerColumn / 8
      Returns:
      the Hilbert index, of length numColumns * bitsPerColumn / 8

    • hilbertIndex

      public static byte[] hilbertIndex(byte[][] columnsBinary, int bitsPerColumn, ByteBuffer reuse, long[] axesReuse, byte[][] transposedReuse)
      Compute the Hilbert index for the given columns, reusing caller-owned scratch space.

      This is the allocation-free variant: callers that convert many rows should hold axesReuse and transposedReuse for the lifetime of the conversion instead of letting every row allocate them, in the same way reuse already avoids a per-row output buffer.

      Parameters:
      columnsBinary - one ordered-byte array per column; each must be at least bitsPerColumn / 8 bytes long (only the leading bytes are used)
      bitsPerColumn - bits taken from each column; a positive multiple of 8, no greater than 64
      reuse - a buffer with capacity at least numColumns * bitsPerColumn / 8
      axesReuse - scratch of length numColumns; contents are overwritten
      transposedReuse - scratch of shape [numColumns][bitsPerColumn / 8]; contents are overwritten
      Returns:
      the Hilbert index, of length numColumns * bitsPerColumn / 8