Hilbert曲线编码

Hilert曲线编码一、Hilbert曲线介绍二、Hilbert编码的意义三、Hilbert编码方法四、Hilbert编码应用一、Hilbert曲线介绍Hilbert曲线是一种能填充满一个平面正方形的分形曲线（空间填充曲线），由德国数学家DavidHilbert在1891年提出。Hilbert曲线的建立过程二、Hilbert编码的意义由于Hilbert编码没有出现大步幅的跳转，所以Hilbert空间排列的聚集性能较好，即Hilbert曲线上相邻的点，在原始空间上一定相邻。传统的空间索引方法多使用R树，四叉树及其改进，算法复杂度高，与传统的B树类一维索引在数据结构上不兼容。通过Hilbert曲线编码方法，可以建立与一维索引统一的多维索引结构。传统的数据划分方法很可能会导致磁盘之间数据存储容量上的不均匀，从而产生严重的数据倾斜现象。利用Hilbert曲线编码可以实现海量空间数据在多磁盘系统上的较均匀分布，从而提高数据查询与检索的并行化程度。此外，Hilbert曲线编码在数据压缩等方面有重要应用。三、Hilbert编码方法对于Hilbert空间填充曲线，标准的平面是一个2n×2n的网格平面（如果是不规则图形，可以先补齐，再编码）。填充这个平面的Hilbert曲线称之为n阶Hilbert填充曲线。3阶Hilbert填充曲线三、Hilbert编码方法对于空间坐标数据变换为Hilbert编码的运算，称之为正运算，f；反之，根据Hilbert编码数据变换为空间坐标数据的运算，称之为逆运算，f-1。经典的Hilbert编码方法是由WarrenM.Lam和JeromeM.Shapiro的按位运算方法。对于一个2n×2n的平面的一点(x,y)。x和y可以用n位数据表示，Hilbert编码值用2n位数据s表示。正运算f的对应表格如下。Hilbert编码正运算按位运算对应表格三、Hilbert编码方法例如对于一个8×8的面上的点(5,4)。首先计算出，阶数n=3。x=5，用二进制表示，x=101，同理，y=100。x[3]=1，y[3]=1，通过查表，可得s[6:5]=10，x[2]=0，y[2]=0，得s[4:3]=00，x[1]=0，y[1]=1，得s[2:1]=01，所以最终s=100001，即s=33。反之，逆运算的对应表格如下。Hilbert编码逆运算按位运算对应表格三、Hilbert编码方法利用上述编码方法得到的8×8平面的Hilbert编码结果如下。0123456758575659606362611415121389101154535255504948511619181730312829202122232427262532353433464744453637383940434241四、Hilbert编码应用利用Hilbert曲线编码进行空间信息数据划分。在《一种面向并行空间数据库的数据划分算法研究》一文中，提出了一种利用Hilbert曲线进行数据划分的方法，有效避免了数据倾斜现象，从而提高了空间数据的检索与查询效率。该算法是在充分考虑空间数据中每个元素个体的数据量不均衡性的基础上进行划分，使得在不同磁盘上存储的实际数据量大小趋近平均，而不是将元素个数进行平均划分。算法的原理如下，将空间数据中每个元素的数据量划分为间对象实体的大小Vi和非空间类型字段值的大小Vother，计算出分为N份后每份理论的数据量Vavg，扫描整个空间数据集，构造Hilbert曲线，为每个空间对象实体赋予Hilbert值，初始化第一个数据集数据=0。然后进行一个累加和比较的过程，按照Hilbert曲线编码顺序累加数据，当累加到某一元素，使得数据集数据量大于Vavg时，在对下一数据集进行累加工作，直到将数据划分完毕。