Zäschke, TilmannNorrie, Moira C.Mitschang, BernhardNicklas, DanielaLeymann, FrankSchöning, HaraldHerschel, MelanieTeubner, JensHärder, TheoKopp, OliverWieland, Matthias2017-06-202017-06-202017978-3-88579-659-6Space 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.enMulti-dimensional indexspatial indexPH-treebinary hypercubeZ-curveZ-orderingwindow queriesText/Conference Paper1617-5468