基于Hilbert曲线与R‑tree的HBase多维查询系统的构建及其查询方法

摘要

本发明公开了一种基于Hilbert曲线与R‑tree的HBase多维查询系统的构建及其查询方法，本发明一方面利用Hilbert曲线对多维数据从多维降到一维，另一方面针对HBase上的多维数据建立R树。映射的一维Hilbert曲线的标志符Hilbert ID能够将信息与原始的高维数据ID建立对应关系。通过R树，高维数据的查询可以高效地映射为一维的Hilbert ID集合。从而实现在HBase上多维数据的快捷查询。

权利要求

1.一种基于Hilbert曲线与R-tree的HBase多维查询系统的构建方法，其特征在于，包括如下步骤：S1、初始化Hilbert编码产生器，根据数据维数N及Hilbert阶数Level，初始化Hilbert编码产生器；

S2、根据数据维数N，初始化R树；

S3、根据用户指定的表名初始化HBase表；

S4：根据多维对象各维属性(a1，a2，......，aN)的值，确定所在网格的网格坐标(x1，x2，......，xN)；

S5、根据网格坐标(x1，x2，......，xN)，确定Hilbert编码HilbertID；

S6、根据网格坐标(x1，x2，......，xN)在R树中查询，若存在数据则不需要插入；否则将网格坐标(x1，x2，......，xN)作为范围，HilbertID作为数据插入到R树中；

S7、对多维对象的各维属性值进行编码，得到字节数组ByteArray；

S8、将多维对象插入到HBase中，其中HilbertID作为RowKey，ID作为列名，ByteArray作为Value；

S9、插入其它多维数据对象重复S4～S8；

S10、结束。

2.根据权利要求1所述的一种基于Hilbert曲线与R-tree的HBase多维查询系统的构建方法，其特征在于，所述步骤S7中的编码方式如下：字节数组前8个字节对应多维对象属性个数的整型值，之后每8个字节表示该多维对象的一个维度属性对应的双精度浮点型值。

3.一种基于Hilbert曲线与R-tree的HBase多维查询系统的查询方法，其特征在于，包括如下步骤：步骤1、根据查询范围确定查询所在网格坐标范围；

步骤2、根据网格范围在R树中查询，得到在查询范围内的HilbertID的集合；

步骤3、对于每一个HilbertID，在HBase中查询，得到字节数组；

步骤4、对步骤3结果进行解码，得到多维对象；

步骤5、对于步骤4查询到的多维对象，根据查询范围进行精确匹配，若多维对象在查询范围内，则将其加入结果集中；如果该对象不在查询范围中，则将其淘汰；

步骤6、结束，结果集中数据即为查询结果。

4.根据权利要求3所述的一种基于Hilbert曲线与R-tree的HBase多维查询系统的查询方法，其特征在于，解码方法如下；读取前8个字节内容，得到多维对象属性数，接着逐一对之后的每8个字节解码为双精度浮点型数据，并赋给多维对象对应属性上。

说明书

基于Hilbert曲线与R-tree的HBase多维查询系统的构建及其

查询方法

技术领域

[0001] 本发明涉及一种基于Hilbert曲线与R-tree的HBase多维查询系统的构建及其查询方法。

背景技术

[0002] 近年来，各种管理数据的技术在不断创新，其中Hadoop开源产品系列在商业实践中取得了广泛认可，几近成为事实上的大数据管理行业标准平台。 Hadoop云计算平台的一个主要特点是可以提供可扩展的计算能力和存储能力，实现交互式的数据查询也是用户所关心的，是云计算成功的关键因素。HBase作为一种NoSQL存储系统，专门设计用来快速随机读写大规模数据。作为Apache Hadoop项目的子项目，一个分布式的、面向列的开源数据库， HBase不同于一般的关系数据库，它是一个适合于非结构化数据存储的数据库，能够很好地解决在数据规模剧增时导致的系统扩展性和存储性能问题，而这些都是传统关系型数据库无法很好应付的。同时，HBase不受限于Hadoop  MapReduce编程框架的高延迟数据处理机制，使得HBase可以满足大规模数据实时处理应用的需求。然而，HBase只有对一维数据的索引，没有多维数据索引。在多维数据查询时只能全表扫描，并使用Filter进行过滤，查询效率低下。易用性和实时性差，难以满足大部分应用需求。

[0003] 随着各种数据库的兴起，空间数据库索引的研究引起了人们越来越多的兴趣和关注，其中1984年Guttman提出的R树是目前最流行的动态空间索引结构，广泛应用于原型研究和商用空间数据库系统。R树是一种层次数据结构，是B树在K维空间上的自然扩展。近年来，很多学者致力于R树的研究，在 R树的基础上衍生出许多变种，比较典型的有R+树，压缩R树等。基于R树索引结构需要解决的主要问题仍然是减少区域的重叠，提高搜索效率。

[0004] 因此针对HBase的数据建立R树索引，可改进HBase的易用性，提升查询性能和效率，节省成本，能极大促进HBase的发展，对大规模数据的存储，分析和管理，以及对社会信息化的发展，都具有现实应用价值和实际意义。

发明内容

[0005] 为解决上述问题，本发明提供了一种基于Hilbert曲线与R-tree的HBase 多维查询系统的构建及其查询方法。

[0006] 为实现上述目的，本发明采取的技术方案为：

[0007] 一种基于Hilbert曲线与R-tree的HBase多维查询系统的构建方法，包括如下步骤：

[0008] S1、初始化Hilbert编码产生器，根据数据维数N及Hilbert阶数Level，初始化Hilbert编码产生器；

[0009] S2、根据数据维数N，初始化R树；

[0010] S3、根据用户指定的表名初始化HBase表；

[0011] S4：根据多维对象各维属性(a1，a2，……，aN)的值，确定所在网格的网格坐标(x1，x2，……，xN)，待管理多维范围为([0，800]，[0，400])，每个网格单元的大小为200*100时，则多维对象o1(250，260)产生的网格坐标为(1，2)。

[0012] S5、根据网格坐标(x1，x2，……，xN)，确定Hilbert编码HilbertID；如多对象o1产生的HilbertID为7。

[0013] S6、根据网格坐标(x1，x2，……，xN)在R树中查询，若存在数据则不需要插入；否则将网格坐标(x1，x2，……，xN)作为范围，HilbertID作为数据插入到R树中；如多维对象o1插入到R树的范围为(1，2)，数据为7。

[0014] S7、对多维对象的各维属性值进行编码，得到字节数组ByteArray；如对象o1编码后的ByteArray为一个24字节的数组，各字节的16进制分别为00 00  00 00 00 00 00 02 40 6f 40 00 00 00 00 00 40 70 40 00 00 00 00 00。

[0015] S8、将多维对象插入到HBase中，其中HilbertID作为RowKey，ID作为列名，ByteArray作为Value；如多维对象o1将插入到HBase中的第7行，第 1列中，Value为24字节数组00 00 00 00 00 00 00 02 40 6f 40 00 00 00 00 00  40 70 40 00 00 00 00 00。

[0016] S9、插入其它多维数据对象重复S4～S8；

[0017] S10、结束。

[0018] 作为优选，所述步骤S7中的编码方式如下：字节数组前8个字节对应多维对象属性个数的整型值，之后每8个字节表示该多维对象的一个维度属性对应的双精度浮点型值。

[0019] 上述的一种基于Hilbert曲线与R-tree的HBase多维查询系统的查询方法，包括如下步骤：

[0020] 步骤1、根据查询范围确定查询所在网格坐标范围；如查询Q1([110，310]， [110，280])，得到的网格坐标范围为([0，1]，[1，2])。

[0021] 步骤2、根据网格范围在R树中查询，得到在查询范围内的HilbertID集合；

[0022] 步骤3、对于每一个HilbertID，在HBase中查询，得到字节数组；如HilbertID＝7时，得到第1列的字节数组00 00 00 00 00 00 00 02 40 6f 40 00 00  00 00 00 40 70 40 00 00 00 00 00。

[0023] 步骤4、对步骤3结果进行解码，得到多维对象；如对字节数组00 00 00 00  00 00 00 02 40 6f 40 00 00 00 00 00 40 70 40 00 00 00 00 00进行解码，得到多维对象维数为2，其属性值为(250，260)

[0024] 步骤5、对于步骤4查询到的多维对象，根据查询范围进行精确匹配，若多维对象在查询范围内，则将其加入结果集中；如果该对象不在查询范围中，则将其淘汰；

[0025] 步骤6、结束，结果集中数据即为查询结果。

[0026] 作为优选，解码方法如下；读取前8个字节内容，得到多维对象属性数，接着逐一对之后的每8个字节解码为双精度浮点型数据，并赋给多维对象对应属性上。

[0027] 本发明一方面利用Hilbert曲线对多维数据从多维降到一维，另一方面针对HBase上的多维数据建立R树。映射的一维Hilbert曲线的标志符HilbertID 能够将信息与原始的高维数据ID建立对应关系。通过R树，高维数据的查询可以高效地映射为一维的HilbertID集合。从而实现在HBase上多维数据的快捷查询。

附图说明

[0028] 图1本发明实施例1中的Hilbert二维编码。

[0029] 图2为本发明实施例1中刚初始化的R树。

[0030] 图3为本发明实施例1各个对象对应的点在网格中的位置。

[0031] 图4为本发明实施例1插入o1后的R树。

[0032] 图5为本发明实施例1插入o2、o3、o4、o5、o6后的R树。

[0033] 图6为本发明实施例1对应的最小边界矩形。

[0034] 图7为本发明实施例1各多维对象及查询范围表示。

具体实施方式

[0035] 为了使本发明的目的及优点更加清楚明白，以下结合实施例对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

[0036] 实施例1

[0037] 本实施例采用5台IBM X3650 M4服务器为测试平台，每台服务器的软硬件配置如下；CPU：2*Xeon E5-2620 CPU(6Cores 12Thread)；内存：32G  Bytes；硬盘：6T Bytes，10000rpm，raid5；操作系统：CentOS 6.4x86_64；开发工具：Eclipse，GNU Toolkits(GCC、G++、GDB)，Vim等；开发语言：Java， C++；Hadoop版本：cloudera hadoop-2.3.0-cdh5.0.1 HBase版本：cloudera hbase-0.96.1.1-cdh5.0.1

[0038] 设待索引对象数据维数为N＝2，待管理多维范围为([0，800]，[0，400])，每个网格单元的大小为200*100，多维数据实例对象有6个，每个数据对象用唯一标识符ID来标识，各个ID对应的点的二维属性如表1所示。

[0039] 表1各个点对象的二维属性

[0040]

[0041] 设查询Q的查询范围为([110，310]，[110，280])。

[0042] 数据插入过程：

[0043] 步骤1：根据已给出的对象数据维数初始化Hilbert编码。本例中N＝2， Level＝2时，Hilbert编码产生器将产生如图1所示的Hilbert二维编码。

[0044] 步骤2：初始化R树。根据数据维数N＝2，初始化R树如图2所示。

[0045] 步骤3：初始化HBase表。根据用户指定的表名初始化HBase表。

[0046] 步骤4：根据多维对象o1各维属性值，确定其所在网格的网格坐标为(1，2)。其他多维对象网格坐标如表2所示。

[0047] 步骤5：根据网格坐标，确定多维对象o1的Hilbert编码为HilbertID＝7。其他各个多维对象对应的HilbertID如表2所示，各个对象在网格中的位置如图3所示。

[0048] 表2各个点对象对应的二维网格坐标及对应的HilbertID

[0049]

[0050] 步骤6：根据o1网格坐标(1，2)在R树中查询，发现不存在，将网格坐标(1，2)作为范围，HilbertID＝7作为数据插入到R树中，如图4所示。

[0051] 步骤7：对多维对象o1的各维属性值进行编码，得到字节数组ByteArray 的各字节的16进制分别为00 00 00 00 00 00 00 02 40 6f 40 00 00 00 00 00  40 70 40 00 00 00 00 00。其他各多维对象对应的ByteArray值如表3所示。

[0052] 表3各多维对象对应ByteArray16进制表示

[0053]

[0054] 步骤8：将多维对象o1将插入到HBase中的第7行，第1列中，Value为 24字节数组00 00 00 00 00 00 00 02 40 6f 40 00 00 00 00 00 40 70 40 00 00  00 00 00。

[0055] 步骤9：重复步骤4-8依次插入多维对象o2、o3、o4、o5、o6，如图5所示；对应的最小边界矩形如图6所示。当插入多维对象执行到步骤6时，因o5的网格坐标已经在R树中存在，故不需要将其插入到R树中。

[0056] 步骤10：结束。

[0057] 数据查询过程：

[0058] 步骤1：由查询Q([110，310]，[110，280])，得到的网格坐标范围为([0， 1]，[1，2])。

[0059] 步骤2：根据网格范围在R树中查询，得到在查询范围内的HilbertID集合的值为{2、7}，如图7 所示。

[0060] 步骤3：对于HilbertID＝7，得到第1列的字节数组00 00 00 00 00 00 00 02  40 6f 40 00 00 00 00 00 40 70 40 00 00 00 00 00。对于HilbertID＝2，得到第4 列的字节数组00 00 00 00 00 00 00 02 40 72 c0 00 00 00 00 00 40 62 c0 00 00  00 00 
00，第5列的字节数组00 00 00 00 00 00 00 02 40 75 e0 00 00 00 00 00  40 64 00 
00 00 00 00 00。

[0061] 步骤4：对步骤3结果进行解码，得到多维对象。各个多维对象解码结果如表4所示。

[0062] 表4各个多维对象解码后对应的属性值

[0063]

[0064]

[0065] Q1([110，310]，[110，280])

[0066] 步骤5：对于步骤4查询到的多维对象，根据查询范围进行精确匹配。多维对象o1与o4在查询范围内，将这两个多维对象插入到结果集中。o5不在查询范围内，将其淘汰。

[0067] 步骤6：结束。结果集{o1，o4}即为查询结果。

[0068] 综上所述，数据插入过程是索引建立过程，二级索引就是R-tree。R-tree 索引中的键值是多维空间坐标，数据值是数据所对应网格单元的HilbertID(数据插入过程、步骤6)，通过R-tree可以将多维查询范围高效地映射为HilbertID 集合(数据查询过程、步骤1、
2)。HilbertID是HBase的行号(数据插入过程、步骤8)，被HBase用于建立一级索引，HilbertID对应的网格单元中的数据都在HBase的同一行。这样就利用Hilbert曲线与R-tree在HBase上进行高效的多维查询。

[0069] 以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以作出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。