3D Hilbert Space Filling Curve Encoding and Decoding Algorithms Based on Efficient Prefix Reduction

JIA Lianyin; FAN Yao; DING Jiaman; LI Xiaowu; YOU Jinguo

doi:10.11999/JEIT230013

Volume 46 Issue 2

Feb. 2024

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2024 > 46(2): 633-642

JIA Lianyin, FAN Yao, DING Jiaman, LI Xiaowu, YOU Jinguo. 3D Hilbert Space Filling Curve Encoding and Decoding Algorithms Based on Efficient Prefix Reduction[J]. Journal of Electronics & Information Technology, 2024, 46(2): 633-642. doi: 10.11999/JEIT230013

Citation:

JIA Lianyin, FAN Yao, DING Jiaman, LI Xiaowu, YOU Jinguo. 3D Hilbert Space Filling Curve Encoding and Decoding Algorithms Based on Efficient Prefix Reduction[J]. Journal of Electronics & Information Technology, 2024, 46(2): 633-642. doi: 10.11999/JEIT230013

Citation:

PDF( 2388 KB)

3D Hilbert Space Filling Curve Encoding and Decoding Algorithms Based on Efficient Prefix Reduction

doi: 10.11999/JEIT230013

JIA Lianyin^{1, 2},
FAN Yao¹,
DING Jiaman^{1
,
,},
LI Xiaowu¹,
YOU Jinguo¹

1.
Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
2.
Key Laboratory of Computer Technology Application of Yunnan Province, Kunming 650500, China

Funds: The National Natural Science Foundation of China (62262035, 62262034, 62062046)

Received Date: 2023-01-12
Rev Recd Date: 2023-06-01

Available Online: 2023-06-20

Publish Date: 2024-02-29

Abstract

Abstract

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 ${2^k} \times {2^k} \times {2^k}$ 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 view,
- Prefix reduction,
- 3D HSFC encoding algorithm,
- 3D HSFC decoding algorithm

FullText(HTML)

References(18)

References

[1]	YAO Zhixin, ZHANG Jianqin, LI Taizeng, et al. A trajectory big data storage model incorporating partitioning and spatio-temporal multidimensional hierarchical organization[J]. ISPRS International Journal of Geo-Information, 2022, 11(12): 621. doi: 10.3390/ijgi11120621.
[2]	LIU Zhaoman, WU Lei, MENG Weizhi, et al. Accurate range query with privacy preservation for outsourced location-based service in IOT[J]. IEEE Internet of Things Journal, 2021, 8(18): 14322–14337. doi: 10.1109/JIOT.2021.3068566.
[3]	ZHANG Xuncai, WANG Lingfei, ZHOU Zheng, et al. A chaos-based image encryption technique utilizing Hilbert curves and H-fractals[J]. IEEE Access, 2019, 7: 74734–74746. doi: 10.1109/ACCESS.2019.2921309.
[4]	CHEN Jiafeng, YU Lu, and WANG Wenyi. Hilbert space filling curve based scan-order for point cloud attribute compression[J]. IEEE Transactions on Image Processing, 2022, 31: 4609–4621. doi: 10.1109/TIP.2022.3186532.
[5]	贾连印, 陈明鲜, 李孟娟, 等. 基于状态视图的高效Hilbert编码和解码算法[J]. 电子与信息学报, 2020, 42(6): 1494–1501. doi: 10.11999/JEIT190501. JIA Lianyin, CHEN Mingxian, LI Mengjuan, et al. State view based efficient Hilbert encoding and decoding algorithms[J]. Journal of Electronics &Information Technology, 2020, 42(6): 1494–1501. doi: 10.11999/JEIT190501.
[6]	BÖHM C, PERDACHER M, and PLANT C. A novel Hilbert curve for cache-locality preserving loops[J]. IEEE Transactions on Big Data, 2021, 7(2): 241–254. doi: 10.1109/TBDATA.2018.2830378.
[7]	贾连印, 孔明, 王维晨, 等. 数据偏斜分布下的二维Hilbert编解码算法[J]. 清华大学学报(自然科学版), 2022, 62(9): 1426–1434. doi: 10.16511/j.cnki.qhdxxb.2021.21.043. JIA Lianyin, KONG Ming, WANG Weichen, et al. 2-D Hilbert encoding and decoding algorithms on skewed data[J]. Journal of Tsinghua University (Science and Technology), 2022, 62(9): 1426–1434. doi: 10.16511/j.cnki.qhdxxb.2021.21.043.
[8]	李绍俊, 钟耳顺, 王少华, 等. 基于状态转移矩阵的Hilbert码快速生成算法[J]. 地球信息科学学报, 2014, 16(6): 846–851. doi: 10.3724/SP.J.1047.2014.00846. LI Shaojun, ZHONG Ershun, WANG Shaohua, et al. An algorithm for Hilbert ordering code based on state-transition matrix[J]. Journal of Geo-Information Science, 2014, 16(6): 846–851. doi: 10.3724/SP.J.1047.2014.00846.
[9]	HAVERKORT H. How many three-dimensional Hilbert curves are there?[J]. Journal of Computational Geometry, 2017, 8(1): 206–281. doi: 10.20382/jocg.v8i1a10.
[10]	WEISSENBÖCK J, FRÖHLER B, GRÖLLER E, et al. Dynamic volume lines: Visual comparison of 3D volumes through space-filling curves[J]. IEEE Transactions on Visualization and Computer Graphics, 2019, 25(1): 1040–1049. doi: 10.1109/TVCG.2018.2864510.
[11]	WU Yuhao, CAO Xuefeng, and AN Zipeng. A spatiotemporal trajectory data index based on the Hilbert curve code[C]. IOP Conference Series: Earth and Environmental Science, Beijing, China, 2020: 012005.
[12]	TSINGANOS P, CORNELIS B, CORNELIS J, et al. Hilbert sEMG data scanning for hand gesture recognition based on deep learning[J]. Neural Computing and Applications, 2021, 33(7): 2645–2666. doi: 10.1007/s00521-020-05128-7.
[13]	陈晓宏, 储飞黄, 方胜良, 等. 基于剖分网格改进A^算法的航迹规划研究[J]. 电光与控制, 2022, 29(7): 17–21. doi: 10.3969/j.issn.1671-637X.2022.07.004. CHEN Xiaohong, CHU Feihuang, FANG Shengliang, et al. Trajectory planning based on A^ algorithm improved by subdivision grid[J]. Electronics Optics &Control, 2022, 29(7): 17–21. doi: 10.3969/j.issn.1671-637X.2022.07.004.
[14]	MOORE D. Fast Hilbert curve generation, sorting, and range queries[EB/OL]. https://github.com/Cheedoong/hilbert, 2021.
[15]	李晨阳, 张杨, 冯玉才. N维Hilbert编码的计算[J]. 计算机辅助设计与图形学学报, 2006, 18(7): 1032–1038. doi: 10.3321/j.issn:1003-9775.2006.07.024. LI Chenyang, ZHANG Yang, and FENG Yucai. Calculation of N-dimensional Hilbert codes[J]. Journal of Computer-Aided Design &Computer Graphics, 2006, 18(7): 1032–1038. doi: 10.3321/j.issn:1003-9775.2006.07.024.
[16]	ZHANG Jian and KAMATA S I. A generalized 3-D Hilbert scan using look-up tables[J]. Journal of Visual Communication and Image Representation, 2012, 23(3): 418–425. doi: 10.1016/j.jvcir.2011.12.005.
[17]	JIA Lianyin, LIANG Binbin, LI Mengjuan, et al. Efficient 3D Hilbert curve encoding and decoding algorithms[J]. Chinese Journal of Electronics, 2022, 31(2): 277–284. doi: 10.1049/cje.2020.00.171.
[18]	ZHENG Yu, XIE Xing, and MA Weiying. GeoLife: A collaborative social networking service among user, location and trajectory[J]. IEEE Data Engineering Bulletin, 2010, 33(2): 32–39.