3D Hilbert Space Filling Curve Encoding and Decoding Algorithms Based on Efficient Prefix Reduction
The encoding and decoding efficiency of 3D Hilbert Space Filling Curve (3D HSFC) is key for the application of spatial query processing, image processing. The existing 3D encoding and decoding algorithms encode and decode each point independently, ignoring the local preservation characteristic of Hilbert curve. To improve the efficiency of encoding and decoding, an efficient 3D state view is designed in this paper, and a new Prefix Reduction 3D HSFC Encoding Algorithm (PR-3HE) and Prefix Reduction 3D HSFC Decoding Algorithm (PR-3HD) are proposed. These two algorithms minimize the orders to be processed through the definition and identification of common prefix, common prefix reduction and various optimization techniques, thus improving 3D HSFC encoding and decoding efficiency. Theoretical proof is provided in this paper,demonstrating that when encoding or decoding a k-order window (all 2k × 2k × 2k points in a window), PR-3HE passively encodes no more than 2 orders for each coordinate on average, while PR-3HD passively decodes no more than 8/7 orders for each Hilbert code on average. The encoding and decoding time complexity can be reduced from O(k) to O(1). Experimental results show on both synthetic and real dataset the benefits of our algorithms over the other counterparts.
3D Hilbert Space Filling Curve (3D HSFC)3D state viewPrefix reduction3D HSFC encoding algorithm3D HSFC decoding algorithm
贾连印、范瑶、丁家满、李晓武、游进国
展开 >
昆明理工大学信息与自动化学院 昆明 650500
云南省计算机应用重点实验室 昆明 650500
3维Hilbert空间填充曲线 3维状态视图 前缀约简 3D HSFC编码算法 3D HSFC解码算法