数据偏斜分布下的二维Hilbert编解码算法  

2-D Hilbert encoding and decoding algorithms on skewed data

作　　者：贾连印[1,3] 孔明 王维晨 李孟娟[2] 游进国[1,3] 丁家满[1,3] JIA Lianyin;KONG Ming;WANG Weichen;LI Mengjuan;YOU Jinguo;DING Jiaman(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China;Library,Yunnan Normal University,Kunming 650500,China;Yunnan Key Laboratory of Artificial Intelligence,Kunming University of Science and Technology,Kunming 650500,China)

机构地区：[1]昆明理工大学信息工程与自动化学院,昆明650500 [2]云南师范大学图书馆,昆明650500 [3]昆明理工大学云南省人工智能重点实验室,昆明650500

出　　处：《清华大学学报（自然科学版）》2022年第9期1426-1434,共9页Journal of Tsinghua University(Science and Technology)

基　　金：国家自然科学基金地区基金项目(62162038,62062046,61562054)。

摘　　要：高效的Hilbert曲线的编解码算法作为Hilbert曲线应用的基础,具有重要的研究意义。现有算法多未考虑数据偏斜分布的影响,因此在数据偏斜分布时效率较低。该文发现:对于特定的前m阶坐标,其对应的前m阶编码值与其第1阶编码值呈现特定的倍数关系;对于特定的前m阶编码值,其对应的前m阶坐标与其第1阶坐标呈现特定的倍数关系。基于这一发现,在融合高效位操作、快速置位检测等技术的基础上,提出了跳过前m阶的编码(skipping the first m orders Hilbert encoding, SFO-HE)算法和跳过前m阶的解码(skipping the first m orders Hilbert decoding, SFO-HD)算法。这2个算法无需对前m阶逐阶编解码,可有效提高数据向Hilbert空间4个顶点偏斜时的编解码效率。扩展实验表明:该文算法对数据偏斜分布具有更好的适应性,在特定偏斜分布时效率大幅优于现有算法。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.

关 键 词：HILBERT曲线 状态视图 偏斜分布 编解码算法 

分 类 号：TN919.8[电子电信—通信与信息系统]