Efficient 3D Hilbert Curve Encoding and Decoding Algorithms

JIA Lianyin; LIANG Binbin; LI Mengjuan; LIU Yong; CHEN Yinong; DING Jiaman

doi:10.1049/cje.2020.00.171

Volume 31 Issue 2

Mar. 2022

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2022 > 31(2): 277-284

JIA Lianyin, LIANG Binbin, LI Mengjuan, et al., “Efficient 3D Hilbert Curve Encoding and Decoding Algorithms,” Chinese Journal of Electronics, vol. 31, no. 2, pp. 277-284, 2022, doi: 10.1049/cje.2020.00.171

Citation:

JIA Lianyin, LIANG Binbin, LI Mengjuan, et al., “Efficient 3D Hilbert Curve Encoding and Decoding Algorithms,” Chinese Journal of Electronics, vol. 31, no. 2, pp. 277-284, 2022, doi: 10.1049/cje.2020.00.171

Citation:

PDF( 3608 KB)

Efficient 3D Hilbert Curve Encoding and Decoding Algorithms

doi: 10.1049/cje.2020.00.171

JIA Lianyin^{1, 2
,},
LIANG Binbin^1
,,
LI Mengjuan^3
,,
LIU Yong^4
,,
CHEN Yinong^5
,,
DING Jiaman^{1, 2
,}

1.
Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
2.
Yunnan Key Laboratory of Artificial Intelligence, Kunming University of Science and Technology, Kunming 650500, China
3.
Library, Yunnan Normal University, Kunming 650500, China
4.
School of Information Science and Engineering, Guangxi University for Nationalities, Nanning 530006, China
5.
School of Computing, Informatics, and Decision Systems, Arizona State University, Tempe 85287, USA

Funds: This work was supported by the National Natural Science Foundation of China (61562054), the Fund of China Scholarship Council (201908530036), and the Talents Introduction Project of Guangxi University for Nationalities (2014MDQD020)

More Information

Author Bio:
was born in 1978. He received his Ph.D. degree from South China University of Technology in 2012. He is currently an Associate Professor in Kunming University of Science and Technology. His research interests include database, data mining, information retrieval, and parallel computing.(Email: lianyinjia@kust.edu.cn)

was born in 1993. He received his M.S. degree from Kunming University of Science and Technology in 2021. He is currently working as a Network Engineer in Ruijie Network Co., Ltd. His research interests include database and data mining.(Email: 2041429702@qq.com)

was born in 1983. She received her M.S. degree in computer science from Kunming University of Science and Technology in 2008. She is currently a Librarian in the Department of Technology, Library, Yunnan Normal University, Kunming, China. Her main research interests include information retrieval and parallel computing.(Email: lmjlykm@163.com)

was born in 1973. He received his Ph.D. degree in engineering from South China University of Technology in 2013. His research interests include bioinformatics, deep learning, and high-performance computing.(Email: niu20060040@gmail.com)

was born in 1961. He received B.S. and M.S. degrees from Chongqing University in computer science in 1982 and 1984, respectively. He received Ph.D. degree from Karlsruhe Institute of Technology, Germany, in 1993. He is currently a Principal Lecturer in the School of Computing and Augmented Intelligence at Arizona State University, USA. His research interests are in service-oriented computing, big data processing, and artificial intelligence.(Email: yinong@asu.edu)

(corresponding author) was born in 1974. He received M.S. degree from Kunming University of Science and Technology in 2005. He is currently an Associate Professor in Kunming University of Science and Technology. His research interests include data mining and cloud computing.(Email: jiamanding@kust.edu.cn)
Received Date: 2020-06-15
Accepted Date: 2020-09-22

Available Online: 2021-10-08

Publish Date: 2022-03-05

Abstract

Abstract

Hilbert curve describes a one-to-one mapping between multidimensional space and 1D space. Most traditional 3D Hilbert encoding and decoding algorithms work on order-wise manner and are not aware of the difference between different input data and spend equivalent computing costs on them, thus resulting in a low efficiency. To solve this problem, in this paper we design efficient 3D state views for fast encoding and decoding. Based on the state views designed, a new encoding algorithm (JFK-3HE) and a new decoding algorithm (JFK-3HD) are proposed. JFK-3HE and JFK-3HD can avoid executing iteratively encoding or decoding each order by skipping the first 0s in input data, thus decreasing the complexity and improving the efficiency. Experimental results show that JFK-3HE and JFK-3HD outperform the state-of-the-arts algorithms for both uniform and skew-distributed data.
- 3D Hilbert curve,
- Space-filling curve,
- state view,
- JFK-3HE,
- JFK-3HD

FullText(HTML)

References(28)

References

[1]	G. Peano, “Sur une courbe, qui remplit toute une aire plane,” Mathematische Annalen, vol.36, pp.157–160, 1890.
[2]	N. Chen, N. Wang and B. Shi, “A new algorithm for encoding and decoding the Hilbert order,” Software Practice & Experience, vol.37, no.8, pp.897–908, 2007.
[3]	S. Ghosh and S. Bhattacharya, “Hilbert curve based steganographic scheme for large data hiding,” Third Int. Conf. on Image Information Processing, pp.91–96, 2015. doi: 10.1109/ICIIP.2015.7414746
[4]	L. F. Cardona and L. E. Múnera, “Self-similarity of space filling curves,” Ingeniería y comptitividad, vol.18, pp.113–124, 2016.
[5]	L. Chen, Y. Gao, X. Li, et al., “Efficient metric indexing for similarity search and similarity joins,” IEEE Transactions on Knowledge and Data Engineering, vol.29, no.3, pp.556–571, 2017. doi: 10.1109/TKDE.2015.2506556
[6]	P. Nagarkar, K. S. Candan and A. Bhat, “Compressed spatial hierarchical bitmap (cSHB) indexes for efficiently processing spatial range query workloads,” Proceedings of the Vldb Endowment, vol.8, pp.1382–1393, 2015. doi: 10.14778/2824032.2824038
[7]	H. Singh and S. Bawa, “A survey of traditional and MapReduceBased spatial query processing approaches,” ACM SIGMOD Record, vol.46, pp.18–29, 2017. doi: 10.1145/3137586.3137590
[8]	H. N. Rad and F. Karimipour, “Representation and generation of space-filling curves: A higher-order functional approach,” Journal of Spatial Science, vol.66, no.3, pp.459–479, 2019. doi: 10.1080/14498596.2019.1668870
[9]	G. Schrack and L. Stocco, “Generation of spatial orders and space-filling curves,” IEEE Transactions on Image Processing, vol.24, no.6, pp.1791–1800, 2015. doi: 10.1109/TIP.2015.2409571
[10]	P. Murali and V. Sankaradass, “An efficient space filling curve based image encryption,” Multimedia Tools and Applications, vol.78, no.2, pp.2135–2156, 2019.
[11]	J. Weissenböck, B. Fröhler, E. Gröller, et al., “Dynamic volume lines: Visual comparison of 3D volumes through space-filling curves,” IEEE Transactions on Visualization and Computer Graphics, vol.25, no.1, pp.1040–1049, 2019. doi: 10.1109/TVCG.2018.2864510
[12]	H. Liu, K. Wang, B. Yang, et al., “Load balancing using hilbert space-filling curves for parallel reservoir simulations,” arXiv preprint, arXiv:1708.01365, 2017.
[13]	Abduljabbar M., Markomanolis G.S., Ibeid H., et al., “Communication reducing algorithms for distributed hierarchical N-body problems with boundary distributions,” ISC High Performance 2017: High Performance Computing, vol.10266, pp.79–96, 2017. doi: 10.1007/978-3-319-58667-0_5
[14]	E. R. Tyercha, G. S. Kazmaier, H. Gildhoff, et al., “Querying spatial data in column stores using tree-order scans,” Patent, Germany, US09613055B2, 2017-04-04.
[15]	Y. W. Dai, G. J. Liu, and S. G. Ye, “Adaptive steganography based on hilbert filling curve,” Acta Electronica Sinica, vol.36, no.S1, pp.35–38, 2008. (in Chinese)
[16]	A. R. Butz, “Alternative algorithm for hilbert’s space-filling curve,” IEEE Trans. Comput., vol.20, pp.424–426, 1971.
[17]	X. Cao, G. Wan, and Z. Zhang, “Compact Hilbert curve index algorithm based on gray code,” Acta Geodaetica Et Cartographica Sinica, vol.45, no.S1, pp.90–98, 2016.
[18]	S. Li, E. Zhong, S. Wang, et al., “An algorithm for Hilbert ordering code based on state-transition matrix,” Journal of Geo-information Science, vol.16, no.6, pp.846–851, 2014.
[19]	J. Burkardt, “Hilbert curve convert between 1D and 2D coordinates of Hilbert curve,” available at: http://people.math.sc.edu/Burkardt/c_src/hilbert_curve/hilbert_curve.html, 2015.
[20]	M. Hu, X. Tian, S. Xia, et al., “Image scrambling based on 3-D Hilbert curve,” 2010 3rd International Congress on Image and Signal Processing, pp.147–149, 2010.
[21]	I. Al-Kharusi and D. W. Walker, “Locality properties of 3D data orderings with application to parallel molecular dynamics simulations,” Int. Journal of High Performance Computing Applications, vol.33, no.5, pp.998–1018, 2019. doi: 10.1177/1094342019846282
[22]	S. Hans, “A three-dimensional Hilbert curve,” International Journal of Mathematical Education in Science and Technology, vol.24, no.4, pp.541–545, 2010.
[23]	R. J. Millar, M. E. C. Hull, and J. H. Frazer, “The millar polyhedron and its use in the construction of octrees,” The Computer Journal, vol.36, no.2, pp.186–194, 1993.
[24]	A. J. Fisher, “A new algorithm for generating hilbert curves,” Software Practice & Experience, vol.16, no.1, pp.5–12, 1986.
[25]	Github, “Fast Hilbert curve generation, sorting, and range queries,” available at: https//github.com/Cheedoong/hilbert, 2016.
[26]	C. Li, X. Duan, and Y. Feng, “N-dimensional Hilbert curve generation algorithm,” Chinese Journal of Image Graphics, vol.11, no.8, pp.1068–1075, 2006.
[27]	J. Zhang and S. I. Kamata, “A generalized 3-D Hilbert scan using look-up tables,” Journal of Visual Communication and Image Representation, vol.23, no.3, pp.418–425, 2012. doi: 10.1016/j.jvcir.2011.12.005
[28]	Rosetta, “Find first and last set bit of a long integer,” available at: https://rosettacode.org/wiki/Find_first_and_last_set_bit_of_a_long_integer, 2019.