首页|高效前缀约简的三维Hilbert空间填充曲线编解码算法

高效前缀约简的三维Hilbert空间填充曲线编解码算法

扫码查看
3维Hilbert空间填充曲线(3D HSFC)的编码和解码效率对空间查询处理、图像处理等领域的应用举足轻重.现有的3维编解码算法独立编解码每一个点,忽略了Hilbert曲线的局部保持特性.为了提高编解码效率,该文设计了高效的3D状态视图,并提出一种新的前缀约简的3D HSFC编码算法(PR-3HE)和前缀约简3D HSFC解码算法(PR-3HD),这两个算法通过公共前缀的定义和识别、公共前缀约简及多种优化技术来最小化需要编码的阶数,从而提高3D HSFC的编解码效率.理论上证明:当编码或解码一个k阶的窗体(窗体内总共含有2k×2k×2k个点)时,PR-3HE平均每个点的编码阶数不超过2,PR-3HD平均解码阶数不超过8/7.相对于传统的基于迭代的方法,编解码时间复杂度从O(k)降低到了.实验结果表明,该文算法在模拟数据集和真实数据集上的表现O(1)显著优于现有算法.
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解码算法

国家自然科学基金国家自然科学基金国家自然科学基金

622620356226203462062046

2024

电子与信息学报
中国科学院电子学研究所 国家自然科学基金委员会信息科学部

电子与信息学报

CSTPCD北大核心
影响因子:1.302
ISSN:1009-5896
年,卷(期):2024.46(2)
  • 18