P265 - BTW2017 - Datenbanksysteme für Business, Technologie und Web

Auflistung nach:

1 - 1 von 1

Konferenzbeitrag
Efficient Z-Ordered Traversal of Hypercube Indexes
(Datenbanksysteme für Business, Technologie und Web (BTW 2017), 2017) Zäschke, Tilmann; Norrie, Moira C.
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.