贾连印^{1, 2},
陈明鲜¹,
李孟娟³,
游进国¹,
丁家满^1,,
1.昆明理工大学信息与自动化学院 昆明 650500
2.云南省计算机应用重点实验室 昆明 650500
3.云南师范大学图书馆技术部 昆明 650500
基金项目:国家自然科学基金(61562054)，国家留学基金委公派留学项目(201908530036)

详细信息

作者简介:贾连印：男，1978年生，副教授，研究方向为数据库、信息检索、并行计算
陈明鲜：男，1994年生，硕士生，研究方向为图像处理、信息检索和自然语言处理
李孟娟：女，1983年生，馆员，研究方向为并行计算和信息检索
游进国：男，1978年生，副教授，研究方向为数据库和数据仓库
丁家满：男，1974年生，副教授，研究方向为数据库和数据挖掘

通讯作者:丁家满　tjom2008@126.com

¹⁾对数据不向原点偏斜的情形，可通过适当的坐标变换，如旋转、平移等，使其尽可能地向原点偏斜。
中图分类号:TN919.81

计量

文章访问数:1114
HTML全文浏览量:428
PDF下载量:40
被引次数:0

出版历程

收稿日期:2019-07-05
修回日期:2020-02-03
网络出版日期:2020-02-27
刊出日期:2020-06-22

State View Based Efficient Hilbert Encoding and Decoding Algorithms

Lianyin JIA^{1, 2},
Mingxian CHEN¹,
Mengjuan LI³,
Jinguo YOU¹,
Jiaman DING^1,,
1. Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
2. Key Laboratory of Computer Technologies Application of Yunnan Province, Kunming 650500, China
3. Library of Yunnan Normal University, Kunming 650500, China
Funds:The National Natural Science Foundation of China (61562054), Fund of China Scholarship Council (201908530036)


摘要
摘要:Hilbert曲线是高维降到1维的重要方法，具有较好的空间聚集和空间连续性，在地理信息系统、空间数据库、信息检索等方面有广泛的应用。现有Hilbert编码或解码算法未考虑输入数据对编码或解码效率的影响，因此将不同输入数据同等对待。为此，该文通过设计高效的状态视图并结合快速置位检测算法提出高效的免计前0的Hilbert编码算法(FZF-HE)和免计前0的Hilbert解码算法(FZF-HD)，可快速识别输入数据前部为0而无需迭代计算的部分，从而降低迭代查询次数及算法复杂度，提高编解码效率。实验结果表明，FZF-HE算法和FZF-HD算法在数据均匀分布时效率稍高于现有算法，而在数据偏斜分布时效率远高于现有算法。
关键词:状态视图/
免计前0的Hilbert编码算法/
免计前0的Hilbert解码算法/
Hilbert曲线
Abstract:Hilbert curve is an important method for high-dimensional reduction to one-dimensional. It has good characteristics of spatial aggregation and spatial continuity and is widely used in geographic information system, spatial databases and information retrieval. Existing Hilbert encoding or decoding algorithms do not consider the differences between input data, thus treating them equally. To this end, an efficient Hilbert coding algorithm Front-Zero-Free Hilbert Encoding(FZF-HE) and an efficient decoding algorithm Front-Zero-Free Hilbert Decoding(FZF-HD) are proposed. FZF-HE and FZF-HD can quickly identify the 0 s of the front part of input data before iterative calculation by combining efficient state views and first bit-1 detection algorithm, thus reducing the number of iterations and the complexity of the algorithm, and improving the encoding and decoding efficiency. The experimental results show that efficiencies of these two algorithms are slightly higher than existing algorithms for uniform distributed data, and are much higher than existing algorithms for skew distributed data.
Key words:State view/
Front-Zero-Free Hilbert Encoding (FZF-HE)/
Front-Zero-Free Hilbert Decoding (FZF-HD)/
Hilbert curve
注释:
1) ¹⁾对数据不向原点偏斜的情形，可通过适当的坐标变换，如旋转、平移等，使其尽可能地向原点偏斜。



PDF全文下载地址:

https://jeit.ac.cn/article/exportPdf?id=ecf10c7f-26f1-4349-91ae-26bde5830f2b