Efficient Z-Ordered Traversal of Hypercube Indexes

Abstract

Space filling curves provide several advantages for indexing spatial data. We look at the Z-curve ordering and discuss three algorithms for navigating and querying k-dimensional Z-curves. In k-dimensional space, a single hyper-’Z’-shape in a recursive Z-curve forms a hypercube with 2k quadrants. The first algorithm concerns e cient checking whether a given quadrant of a local hyper-’Z’ intersects with a global query hyper-box. The other two algorithms allow e cient Z-ordered traversal through the intersection space, either based on a predecessor from inside the intersection (second algorithm) or from any predecessor (third algorithm). The algorithms require an initialisation phase of ⇥(k) for encoding the intersection envelope of the local hyper-’Z’ with a range query. Using this envelope, all three algorithms then execute in ⇥(1). The algorithms are however limited by the register width of the CPU at hand, for example to k < 64 on a 64 bit CPU.