Research on Continuity of Multi-scale Space-filling Curves

ZHAI Weixin1, CHEN Bo2, TONG Xiaochong3, CHENG Chengqi2,†

1. Institute of Remote Sensing and Geographic Information System, Peking University, Beijing 100871; 2. Aerospace Information Engineering Research Center, Peking University, Beijing 100871; 3. Institute of Survey and Mapping, Information Engineering University, Zhengzhou 450001; † Corresponding author, E-mail: ccq@pku.edu.cn

Abstract Multi-scale two-dimensional Hilbert curve is constructed, and specially the scale dimension is treated as the third dimension. The new structure embodies the multi-level characteristics and overcomes the drawback of Z sequence coding pattern, thus improving the continuity of the curve and advancing the spatial retrieval efficiency. The authors conducted two kinds of experiments based on the quad-tree model to compare the retrieval efficiency of Hilbert curve and Z curve. The consequence indicates that the multi-scale Hilbert curve performs better than Z curve, and the improvement on different data distributions vary from 15% to 30%. Key words multi-scale; Hilbert curve; spatial continuity

随着空间数据获取方式的不断进步, 多源、多类型的空间数据急剧增长, 但空间数据的组织仍面临许多实际问题, 尤其是空间数据编码的问题, 给实际应用带来极大的挑战。地球剖分理论提出一套空间数据的统一编码体系, 为解决此类问题提供了可行的解决方案[1–2]。

在地球剖分的体系内, 建立合理的空间索引结构能够优化空间数据库的各类操作。在目前空间数据量高速增长的情况下, 对于空间索引效率的提高尤为重要。二维空间中的四叉树索引是一种常见的空间索引结构, 1974 年由 Finkel 等[3]提出, 四叉树

的基本思想是, 将地理信息的规划分为不同层次的树结构, 将每一级的全空间等分为 4 个子空间, 直至达到最高层级为止。传统的四叉树索引的编码以二维的 Z 曲线为基础[4–5], 也有学者提出线性四叉树等编码方式, 并应用于空间库索引结构, 提高了查询效率[6]。空间填充曲线的空间连续性用于描述在空间上连续的地理实体被空间填充曲线转化为一维数值编码后编码的连续性状况。对于同样的地理实体, 转化后的编码间隔数越小, 该空间填充曲线的空间连续性越好。