Konferenzbeitrag
Efficient Z-Ordered Traversal of Hypercube Indexes
Lade...
Volltext URI
Dokumententyp
Text/Conference Paper
Dateien
Datum
2017
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Quelle
Datenbanksysteme für Business, Technologie und Web (BTW 2017)
Index Structures
Verlag
Gesellschaft für Informatik, Bonn
Zusammenfassung
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.