Efficient Z-Ordered Traversal of Hypercube Indexes
ISSN der Zeitschrift
Datenbanksysteme für Business, Technologie und Web (BTW 2017)
Gesellschaft für Informatik, Bonn
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.