Acta Geodaetica et Cartographica Sinica (Dec 2016)

Compact Hilbert Curve Index Algorithm Based on Gray Code

  • CAO Xuefeng,
  • WAN Gang,
  • ZHANG Zongpei

DOI
https://doi.org/10.11947/j.AGCS.2016.F010
Journal volume & issue
Vol. 45, no. S1
pp. 90 – 98

Abstract

Read online

Hilbert curve has best clustering in various kinds of space filling curves, and has been used as an important tools in discrete global grid spatial index design field. But there are lots of redundancies in the standard Hilbert curve index when the data set has large differences between dimensions. In this paper, the construction features of Hilbert curve is analyzed based on Gray code, and then the compact Hilbert curve index algorithm is put forward, in which the redundancy problem has been avoided while Hilbert curve clustering preserved. Finally, experiment results shows that the compact Hilbert curve index outperforms the standard Hilbert index, their 1 computational complexity is nearly equivalent, but the real data set test shows the coding time and storage space decrease 40%, the speedup ratio of sorting speed is nearly 4.3.

Keywords