Bos, Arie ;
Haverkort, Herman J.
Hyperorthogonal WellFolded Hilbert Curves
Abstract
Rtrees can be used to store and query sets of point data in two or more dimensions. An easy way to construct and maintain Rtrees for twodimensional points, due to Kamel and Faloutsos, is to keep the points in the order in which they appear along the Hilbert curve. The Rtree will then store bounding boxes of points along contiguous sections of the curve, and the efficiency of the Rtree depends on the size of the bounding boxes  smaller is better. Since there are many different ways to generalize the Hilbert curve to higher dimensions, this raises the question which generalization results in the smallest bounding boxes. Familiar methods, such as the one by Butz, can result in curve sections whose bounding boxes are a factor Omega(2^{d/2}) larger than the volume traversed by that section of the curve. Most of the volume bounded by such bounding boxes would not contain any data points. In this paper we present a new way of generalizing Hilbert's curve to higher dimensions, which results in much tighter bounding boxes: they have at most 4 times the volume of the part of the curve covered, independent of the number of dimensions. Moreover, we prove that a factor 4 is asymptotically optimal.
BibTeX  Entry
@InProceedings{bos_et_al:LIPIcs:2015:5096,
author = {Arie Bos and Herman J. Haverkort},
title = {{Hyperorthogonal WellFolded Hilbert Curves}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {812826},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897835},
ISSN = {18688969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5096},
URN = {urn:nbn:de:0030drops50962},
doi = {10.4230/LIPIcs.SOCG.2015.812},
annote = {Keywords: spacefilling curve, Hilbert curve, multidimensional, range query, Rtree}
}
2015
Keywords: 

spacefilling curve, Hilbert curve, multidimensional, range query, Rtree 
Seminar: 

31st International Symposium on Computational Geometry (SoCG 2015)

Issue date: 

2015 
Date of publication: 

2015 