Logo des Repositoriums
 

Efficient Z-Ordered Traversal of Hypercube Indexes

Kurzanzeige
dc.contributor.authorZäschke, Tilmann
dc.contributor.authorNorrie, Moira C.
dc.contributor.editorMitschang, Bernhard
dc.contributor.editorNicklas, Daniela
dc.contributor.editorLeymann, Frank
dc.contributor.editorSchöning, Harald
dc.contributor.editorHerschel, Melanie
dc.contributor.editorTeubner, Jens
dc.contributor.editorHärder, Theo
dc.contributor.editorKopp, Oliver
dc.contributor.editorWieland, Matthias
dc.date.accessioned2017-06-20T20:24:33Z
dc.date.available2017-06-20T20:24:33Z
dc.date.issued2017
dc.description.abstractSpace 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.en
dc.identifier.isbn978-3-88579-659-6
dc.identifier.pissn1617-5468
dc.language.isoen
dc.publisherGesellschaft für Informatik, Bonn
dc.relation.ispartofDatenbanksysteme für Business, Technologie und Web (BTW 2017)
dc.relation.ispartofseriesLecture Notes in Informatics (LNI) - Proceedings, Volume P-265
dc.subjectMulti-dimensional index
dc.subjectspatial index
dc.subjectPH-tree
dc.subjectbinary hypercube
dc.subjectZ-curve
dc.subjectZ-ordering
dc.subjectwindow queries
dc.titleEfficient Z-Ordered Traversal of Hypercube Indexesen
dc.typeText/Conference Paper
gi.citation.endPage484
gi.citation.startPage465
gi.conference.date6.-10. März 2017
gi.conference.locationStuttgart
gi.conference.sessiontitleIndex Structures

Dateien

Originalbündel
1 - 1 von 1
Vorschaubild
Name:
paper30.pdf
Größe:
576.38 KB
Format:
Adobe Portable Document Format
Herunterladen

Sammlungen

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