高级搜索

基于状态视图的高效Hilbert编码和解码算法

贾连印 陈明鲜 李孟娟 游进国 丁家满

引用本文: 贾连印, 陈明鲜, 李孟娟, 游进国, 丁家满. 基于状态视图的高效Hilbert编码和解码算法[J]. 电子与信息学报, doi: 10.11999/JEIT190501 shu
Citation:  Lianyin JIA, Mingxian CHEN, Mengjuan LI, Jinguo YOU, Jiaman DING. State View Based Efficient Hilbert Encoding and Decoding Algorithms[J]. Journal of Electronics and Information Technology, doi: 10.11999/JEIT190501 shu

基于状态视图的高效Hilbert编码和解码算法

    作者简介: 贾连印: 男,1978年生,副教授,研究方向为数据库、信息检索、并行计算;
    陈明鲜: 男,1994年生,硕士生,研究方向为图像处理、信息检索和自然语言处理;
    李孟娟: 女,1983年生,馆员,研究方向为并行计算和信息检索;
    游进国: 男,1978年生,副教授,研究方向为数据库和数据仓库;
    丁家满: 男,1974年生,副教授,研究方向为数据库和数据挖掘
    通讯作者: 丁家满,tjom2008@126.com
  • 基金项目: 国家自然科学基金(61562054),国家留学基金委公派留学项目(201908530036)

摘要: Hilbert曲线是高维降到1维的重要方法,具有较好的空间聚集和空间连续性,在地理信息系统、空间数据库、信息检索等方面有广泛的应用。现有Hilbert编码或解码算法未考虑输入数据对编码或解码效率的影响,因此将不同输入数据同等对待。为此,该文通过设计高效的状态视图并结合快速置位检测算法提出高效的免计前0的Hilbert编码算法(FZF-HE)和免计前0的Hilbert解码算法(FZF-HD),可快速识别输入数据前部为0而无需迭代计算的部分,从而降低迭代查询次数及算法复杂度,提高编解码效率。实验结果表明,FZF-HE算法和FZF-HD算法在数据均匀分布时效率稍高于现有算法,而在数据偏斜分布时效率远高于现有算法。

English

    1. [1]

      GUNTHER S and STOCCO L. Generation of spatial orders and space-filling curves[J]. IEEE Transactions on Image Processing, 2015, 24(6): 1791–1800. doi: 10.1109/TIP.2015.2409571

    2. [2]

      周映虹, 马争鸣. 基于层次模型的重要性编码算法[J]. 电子与信息学报, 2009, 31(6): 1497–1500.
      ZHOU Yinghong and MA Zhengming. A significance coding algorithm based on layer model[J]. Journal of Electronics &Information Technology, 2009, 31(6): 1497–1500.

    3. [3]

      CHEN Lu, GAO Yunjun, LI Xinhan, et al. Efficient metric indexing for similarity search and similarity joins[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(3): 556–571. doi: 10.1109/TKDE.2015.2506556

    4. [4]

      SINGH H and BAWA S. A survey of traditional and mapReduceBased spatial query processing approaches[J]. ACM SIGMOD Record, 2017, 46(2): 18–29. doi: 10.1145/3137586.3137590

    5. [5]

      ABDULJABBAR M, MARKOMANOLIS G S, IBEID H, et al. Communication reducing algorithms for distributed hierarchical N-Body problems with boundary distributions[C]. The 32nd International Supercomputing Conference, Frankfurt, Germany, 2017: 79–96.

    6. [6]

      LIU Hui, WANG Kun, YANG Bo, et al. Dynamic load balancing using hilbert space-filling curves for parallel reservoir simulations[C]. The SPE Reservoir Simulation Conference, Montgomery, USA, 2017. doi: 10.2118/182613-MS.

    7. [7]

      HAN Guangjie, XUAN Xuan, LIU Li, et al. A disaster management-oriented path planning for mobile anchor node-based localization in wireless sensor networks[J]. IEEE Transactions on Emerging Topics in Computing, 2020. doi: 10.1109/TETC.2017.2687319

    8. [8]

      KONG Lingping, PAN J S, SUNG T W, et al. An energy balancing strategy based on hilbert curve and genetic algorithm for wireless sensor networks[J]. Wireless Communications and Mobile Computing, 2017, 2017: 5720659.

    9. [9]

      BOHM C, PERDACHER M, and PLANT C. A novel hilbert curve for cache-locality preserving loops[J]. IEEE Transactions on Big Data, $ref.ref_year. doi: 10.1109/TBDATA.2018.2830378

    10. [10]

      MORTON G M. A computer oriented geodetic data base and a new technique in file sequencing[EB/OL]. https://domino.research.ibm.com/library/cyberdig.nsf/0/0dabf9473b9c86d48525779800566a39?OpenDocument, 1966.

    11. [11]

      BUTZ A R. Alternative algorithm for Hilbert's space-filling curve[J]. IEEE Transactions on Computers, 1971, C-20(4): 424–426. doi: 10.1109/T-C.1971.223258

    12. [12]

      MOON B, JAGADISH H V, FALOUTSOS C, et al. Analysis of the clustering properties of the hilbert space-filling curve[J]. IEEE Transactions on Knowledge and Data Engineering, 2001, 13(1): 124–141. doi: 10.1109/69.908985

    13. [13]

      NAGARKAR P, CANDAN K S, and BHAT A. Compressed spatial hierarchical bitmap (cSHB) indexes for efficiently processing spatial range query workloads[J]. Proceedings of the VLDB Endowment, 2015, 8(12): 1382–1393. doi: 10.14778/2824032.2824038

    14. [14]

      CHRISTOFORAKI M, HE Jinru, DIMOPOULOS C, et al. Text vs. space: Efficient geo-search query processing[C]. The 20th ACM International Conference on Information and Knowledge Management, Glasgow, UK, 2011: 423–432.

    15. [15]

      FISHER A J. A new algorithm for generating Hilbert curves[J]. Practice and Experience, 1986, 16(1): 5–12. doi: 10.1002/spe.4380160103

    16. [16]

      李绍俊, 钟耳顺, 王少华, 等. 基于状态转移矩阵的Hilbert码快速生成算法[J]. 地球信息科学学报, 2014, 16(6): 846–851.
      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.

    17. [17]

      XCTORRES. Hilbert_spatial_index[EB/OL]. https://github.com/xcTorres/hilbert_spatial_index, 2017.

    18. [18]

      BURKARDT J. HILBERT_CURVE convert between 1D and 2D coordinates of Hilbert curve[EB/OL]. http://people.math.sc.edu/Burkardt/c_src/hilbert_curve/hilbert_curve.html, 2015.

    19. [19]

      MOORE D. Fast Hilbert curve generation, sorting, and range queries[EB/OL]. https://github.com/Cheedoong/hilbert, 2016.

    20. [20]

      曹雪峰, 万刚, 张宗佩. 紧致的Hilbert曲线Gray码索引算法[J]. 测绘学报, 2016, 45(S1): 90–98. doi: 10.11947/j.AGCS.2016.F010
      CAO Xuefeng, WAN Gang, and ZHANG Zongpei. Compact Hilbert curve index algorithm based on Gray code[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(S1): 90–98. doi: 10.11947/j.AGCS.2016.F010

    21. [21]

      LI R. Hilbert range query decomosition[EB/OL]. https://github.com/cloudray8580/Hilbert RangeQueryDecomosition, 2019.

    22. [22]

      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

    23. [23]

      LIU Hui, CUI Tao, LENG Wei, et al. Encoding and decoding algorithms for arbitrary dimensional Hilbert order[J]. arXiv: 1601.01274, 2016.

    24. [24]

      刘辉, 冷伟, 崔涛. 高维Hilbert曲线的编码与解码算法设计[J]. 数值计算与计算机应用, 2015, 36(1): 42–58.
      LIU Hui, LENG Wei, and CUI Tao. Development of encoding and decoding algorithms for high dimensional Hilbert curves[J]. Journal on Numerical Methods and Computer Applications, 2015, 36(1): 42–58.

    25. [25]

      ROSETTA. Find first and last set bit of a long integer[EB/OL]. http://rosettacode.org/wiki/Find_first_and_last_set_bit_of_a_long_integer, 2019.

    1. [1]

      张建, 关键, 董云龙, 何友. 基于局部Hilbert谱平均带宽的微弱目标检测算法. 电子与信息学报,

    2. [2]

      盖强, 殷福亮. 二维Hilbert-Huang变换的分解方法研究. 电子与信息学报,

    3. [3]

      黄国策, 王桂胜, 任清华, 董淑福, 高维廷, 魏帅. 基于Hilbert信号空间的未知干扰自适应识别方法. 电子与信息学报,

    4. [4]

      王宏建, 高本庆. Hilbert分形天线及其全波分析. 电子与信息学报,

    5. [5]

      蔡毓, 刘贵忠, 侯兴松. 基于二进小波变换的实信号的多尺度Hilbert变换和瞬时频率提取. 电子与信息学报,

    6. [6]

      刘高高, 张林让, 刘昕, 刘楠, 陈广锋, 张波. 一种曲线轨迹下的大场景前斜视成像算法. 电子与信息学报,

    7. [7]

      许家栋. 多状态反射计技术. 电子与信息学报,

    8. [8]

      刘凯, 余君君, 黄青华. 基于压缩感知的免携带设备双目标定位算法. 电子与信息学报,

    9. [9]

      王峰, 向新, 易克初, 熊磊. L0范数平滑逼近的稳健求解算法. 电子与信息学报,

    10. [10]

      郑岱堃, 王首勇, 杨军, 杜鹏飞. 一种基于二阶Markov目标状态模型的多帧关联动态规划检测前跟踪算法. 电子与信息学报,

    11. [11]

      李炳成, 沈俊. 曲线矩不变性的研究. 电子与信息学报,

    12. [12]

      邹益民, 汪渤. 基于单视图像的球体姿态估计. 电子与信息学报,

    13. [13]

      张艳, 安平, 尤志翔, 张兆杨. 基于边缘差异的虚拟视图像质量评价方法. 电子与信息学报,

    14. [14]

      曲庆, 金坚, 谷源涛. 用于稀疏系统辨识的改进l0-LMS算法. 电子与信息学报,

    15. [15]

      孙娜, 刘继文, 肖东亮. 基于BFGS拟牛顿法的压缩感知SL0重构算法. 电子与信息学报,

    16. [16]

      杨威, 黄刘生, 王启研. 基于椭圆曲线的三方比特承诺. 电子与信息学报,

    17. [17]

      刘胜利, 杨波, 王育民. 基于椭圆曲线密码体制的投票协议. 电子与信息学报,

    18. [18]

      刘浩杰, 杜利民, 付跃文. 韵律块基频曲线的优化及规则. 电子与信息学报,

    19. [19]

      张猛, 徐茂智, 胡志, 侯英. 构造小嵌入次数的椭圆曲线参数化族. 电子与信息学报,

    20. [20]

      张方国, 王常杰, 王育民. GF(p)上安全椭圆曲线及其基点的选取. 电子与信息学报,

  • 图 1  1阶、2阶和3阶Hilbert曲线示意图

    图 2  1阶Hilbert曲线对应的4种状态

    图 3  均匀分布下编码效率对比

    图 4  $\beta $对编码效率的影响

    图 5  $\alpha $对编码效率的影响

    图 6  均匀分布下解码效率对比

    图 7  $\beta $对解码效率的影响

    图 8  $\alpha $对解码效率的影响

    表 1  编码状态视图

    状态0000111122223333
    坐标00011011000110110001101100011011
    编码00011110001101101011010010011100
    下阶状态1030021121233302
    下载: 导出CSV

    表 2  解码状态视图

    状态0000111122223333
    编码00011011000110110001101100011011
    坐标00011110001011011110000111010010
    下阶状态1003011232212330
    下载: 导出CSV

    表 3  FZF-HE算法

     输入:X,横坐标
        Y,纵坐标
        n,阶
     输出:Hilbert编码$Z$
     (1) Z←0
     (2) $p$←${\rm{msb}}(\max(X,Y))$//置位检测
     (3) $t$←($n$-$p$-1)%2//计算第$n$-$p$阶状态
     (4) for $i$ from $n$-$p$ to $n$
     (5) $Z{\rm{ = }}Z{{ < < 2 | {\rm{Key}}[}}t{\rm{][}}{x_i}{\rm{][}}{y_i}{\rm{] }}$//查Key视图
     (6) $t{\rm{ = Type[}}t{\rm{][}}{x_i}{\rm{][}}{y_i}{\rm{]}}$//查Type视图
    下载: 导出CSV

    表 4  FZF-HD算法

     输入:$Z$,Hilbert编码
        n,阶
     输出:X,横坐标
        Y,纵坐标
     (1) $X$, $Y$←0
     (2) $p$←${\rm{msb}}(Z)$//置位检测
     (3) $t$←($n$-$p$/2-1)//计算第$n$-$p$/2阶状态
     (4) for $i$ from $n$-$p$/2 to $n$
     (5) ${\rm{coord}} = {\rm{InvKey}}[t][{z_{2i - 1}}{z_{2i}}]$ //查InvKey视图
     (6) $ Y = Y < < 1 | {\rm{coord}} \& 0{\rm{x}}1 $
       $ X = X < < 1 | {\rm{coord}} > > 1\& 0{\rm{x}}1 $
     (7) $t = {\rm{InvType}}[t][{z_{2i - 1}}{z_{2i}}]$//查InvType视图
    下载: 导出CSV
  • 加载中
图(8)表(4)
计量
  • PDF下载量:  9
  • 文章访问数:  102
  • HTML全文浏览量:  67
文章相关
  • 通讯作者:  丁家满, tjom2008@126.com
  • 收稿日期:  2019-07-05
  • 录用日期:  2020-02-03
  • 网络出版日期:  2020-02-27
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章