@article{JIA2022, 
author = {Lianyin JIA and Ming KONG and Weichen WANG and Mengjuan LI and Jinguo YOU and Jiaman DING},
title = {2-D Hilbert encoding and decoding algorithms on skewed data},
year = {2022},
journal = {Journal of Tsinghua University (Science and Technology)},
volume = {62},
number = {9},
pages = {1426-1434},
keywords = {Hilbert curve, state view, skewed distribution, encoding and decoding algorithms},
url = {https://www.sciopen.com/article/10.16511/j.cnki.qhdxxb.2021.21.043},
doi = {10.16511/j.cnki.qhdxxb.2021.21.043},
abstract = {Hilbert encoding and decoding are fundamental steps in many Hilbert curve based applications. However, existing algorithms are not very efficient when the data distribution is skewed. This paper shows that for a coordinate with the specific first m orders, the code of the first m orders is a multiple of its corresponding first order code. For a code with the specific first m orders, the coordinate of the first m orders is a multiple of its corresponding first order coordinate. These findings were used to develop an algorithm that skips the first m orders of the Hilbert encoding (SFO-HE) and another algorithm that skips the first m orders of the Hilbert decoding (SFO-HD). These algorithms exploit efficient bit operations and fast bit set detections to improve the encoding and decoding efficiencies for data skewed to the 4 corners of the Hilbert space. Extensive tests show that these two algorithms have good skewness adaptability and outperform existing algorithms on specific skewed data.}
}