Hyperorthogonal Well-Folded Hilbert Curves

Authors Arie Bos, Herman J. Haverkort



PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.812.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Arie Bos
Herman J. Haverkort

Cite AsGet BibTex

Arie Bos and Herman J. Haverkort. Hyperorthogonal Well-Folded Hilbert Curves. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 812-826, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.SOCG.2015.812

Abstract

R-trees can be used to store and query sets of point data in two or more dimensions. An easy way to construct and maintain R-trees for two-dimensional points, due to Kamel and Faloutsos, is to keep the points in the order in which they appear along the Hilbert curve. The R-tree will then store bounding boxes of points along contiguous sections of the curve, and the efficiency of the R-tree 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.
Keywords
  • space-filling curve
  • Hilbert curve
  • multi-dimensional
  • range query
  • R-tree

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. J. Alber and R. Niedermeier. On multidimensional curves with Hilbert property. Theory of Computing Systems, 33(4):295-312, 2000. Google Scholar
  2. L. Arge, M. de Berg, H. Haverkort, and K. Yi. The Priority R-tree: a practically efficient and worst-case optimal R-tree. ACM Tr. Algorithms, 4(1):9, 2008. Google Scholar
  3. M. Bader. Space-filling curves: an introduction with applications in scientific computing. Springer, 2013. Google Scholar
  4. A. R. Butz. Alternative algorithm for Hilbert’s space-filling curve. IEEE Trans. Comp., 20(4):424-426, 1971. Google Scholar
  5. H. Haverkort. An inventory of three-dimensional Hilbert space-filling curves. CoRR, abs/1109.2323, 2011. Google Scholar
  6. H. Haverkort. Harmonious Hilbert curves and other extradimensional space-filling curves. CoRR, abs/1211.0175, 2012. Google Scholar
  7. H. Haverkort and F. van Walderveen. Locality and bounding-box quality of two-dimensional space-filling curves. Computational Geometry, 43(2):131-147, 2010. Google Scholar
  8. H. Haverkort and F. van Walderveen. Four-dimensional Hilbert curves for R-trees. ACM J. Experimental Algorithmics, 16:3.4, 2011. Google Scholar
  9. D. Hilbert. Über die stetige Abbildung einer Linie auf ein Flächenstück. Math. Ann., 38(3):459-460, 1891. Google Scholar
  10. I. Kamel and C. Faloutsos. On packing R-trees. In Conf. on Information and Knowledge Management, pages 490-499, 1993. Google Scholar
  11. K. V. R. Kanth and A. K. Singh. Optimal dynamic range searching in non-replicating index structures. In Int. Conf. Database Theory, LNCS 154, pages 257-276, 1999. Google Scholar
  12. Y. Manolopoulos, A. Nanopoulos, A. N. Papadopoulos, and Y. Theodoridis. R-trees: Theory and Applications. Springer, 2005. Google Scholar
  13. D. Moore. Fast Hilbert curve generation, sorting, and range queries. http://web.archive.org/web/www.caam.rice.edu/~dougm/twiddle/Hilbert/, 2000, retrieved 23 March 2015.
  14. G. Peano. Sur une courbe, qui remplit toute une aire plane. Math. Ann., 36(1):157-160, 1890. Google Scholar
  15. H. Sagan. Space-Filling Curves. Universitext. Springer, 1994. Google Scholar
  16. S. Sasburg. Approximating average and worst-case quality measure values for d-dimensional space-filling curves. Master’s thesis, Eindhoven University of Technology, 2011. Google Scholar
  17. J.-M. Wierum. Definition of a new circular space-filling curve: βΩ-indexing. Technical Report TR-001-02, Paderborn Center for Parallel Computing PC², 2002. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail