一种基于MapReduce的最邻近空间集合关键字查询方法

摘要

本发明公开了一种基于MapReduce的最邻近空间集合关键字查询方法，基于Hadoop框架，使用实时建立的分布式Hilbert R‑树索引的方式，采用了两点配对算法结合叶子节点对角线剪枝方法与圆扫描剪枝方法完成了快速的空间集合关键字的查询，并在地图应用中进行了实验。实验结果表明分布式Hilbert R‑树索引的设计，可以有效减小索引体量，应对异构数据源与数据快速更新的情况；两点配对算法可以极大削减检索空间，加快系统的响应速度，促进了集合空间关键词查询的实用化。

说明书

技术领域

本发明属于数据查询技术领域，具体涉及一种最邻近空间集合关键字查询方法。

背景技术

随着定位技术的出现和移动设备的普及，许多网页，社交网络和其他数据都添加了“位置”标签，基于关键字和位置匹配的空间关键词查询在网络上迅速增长，极大的丰富了基于地图的位置服务的资源，改变了人们在日常生活中位置查询的方式，更好的服务了人们的生活。在各种基于关键字的位置信息查询中，单一关键字查询较为常见，比如在百度地图中搜索“加油站”或“便利店”等。随着请求的日益复杂，多个关键字被一个空间对象所包含变得越来越难，查询目标逐渐从一个空间对象变成多个空间对象的集合，比如查询{“加油站”，“餐馆”}可以找到相距较近的位置区域。

这种从单一对象到对象所在区域的查找方法也被称为空间集合查询，近年来引起了研究人员的关注。由于传统区域数据库的存储和计算能力有限，因此在大型数据的环境下的空间集合查询仍处于理论研究中，未存在成熟的基于地图的空间集合查询应用。

面向大数据的空间对象查询的方法主要包括以下两种：1)直接应用现有环境进行大数据的并行计算以解决空间查询问题，例如MapReduce解决K-NN查询；2)扩展现有大数据系统以解决空间范围查询问题，例如基于Hadoop的TAREEG解决空间查询问题以及MoDisSENSE解决时间和空间等级查询问题。当前面向大数据的集合空间关键字查询主要在研究阶段，并未有相关实际的应用，原因在于查询算法多采用直接组合的方式进行大数据环境下的算法实现；并且现有算法均假设空间索引与倒排索引已经完成，在数据更新快，数据量大，实时性上仍有较大的缺陷。

Hilbert R-树是建立在R-树基本结构上的一种有效的索引结构，使用希尔伯特曲线的优秀聚集性质，将高维数据映射到一维上，保存大部分空间信息，实现R-树数据的有效编制。该方法具有快速树结构、外部存储器存取少，易于并行处理的特征。Hilbert R-树适用于处理不均匀分散的点数据集的情况。对于实际的点数据来说，Hilbert R-树的构建分为静态的和动态的。

发明内容

为了克服现有技术的不足，本发明提供了一种基于MapReduce的最邻近空间集合关键字查询方法，基于Hadoop框架，使用实时建立的分布式Hilbert R-树索引的方式，采用了两点配对算法结合叶子节点对角线剪枝方法与圆扫描剪枝方法完成了快速的空间集合关键字的查询，并在地图应用中进行了实验。实验结果表明分布式Hilbert R-树索引的设计，可以有效减小索引体量，应对异构数据源与数据快速更新的情况；两点配对算法可以极大削减检索空间，加快系统的响应速度，促进了集合空间关键词查询的实用化。

本发明解决其技术问题所采用的技术方案包括如下步骤：

步骤1：地图位置对象数据的格式包含：1)数据所包含的关键字；2)数据的经纬度坐标；所有数据存放在HDFS中；

步骤2：设置查询关键字，从HDFS的block读取对象数据，对象数据读取过程中，根据对象数据包含的关键字，将符合查询条件的对象数据放在内存中，并根据查询关键字生成该对象数据的keyBit，keyBit是表示对象数据包含关键字的二进制代码；然后序列化HilbertCurve对象，根据HilbertCurve对象的经纬度坐标求出其Hilbert value，建立Hilbert R-树，并将Hilbert R-树传给所有的计算节点；

步骤3：叶子节点对角线剪枝方法；

步骤3-1：生成一个叶子节点，判断该叶子节点所包含的查询关键字，如果该叶子节点包含所有查询关键字，那么将该叶子节点的对角线距离设置为阈值；

步骤3-2：重复步骤3-1，如果新生成的叶子节点包含所有的查询关键字，且对角线距离小于阈值，则用新生成的叶子节点的对角线距离更新阈值，直到所有的叶子节点全部生成完；最终得到的阈值记为S；

步骤4：圆扫描剪枝方法；

遍历所有对象数据，以数据对象为圆心，

步骤5：遍历剩余对象数据，采用两点配对法进行对象数据的两两配对，形成对象对；

步骤6：对象配对方法；

步骤6-1：用Hilbert R-树的根节点与自身配对；

步骤6-2：对于非叶子节点对，列举所有的子节点对，如果两个节点所对应的矩形的最小距离大于S，则忽略该节点对，否则继续进行子节点进行配对；对于叶子节点对，列举所有的对象对；

步骤6-3：重复6-2，直到所有的对象对都配对完成；

步骤7：如果对象对的距离小于阈值S，则将对象对的距离设为key，两个对象数据作为value输出给reduce；

步骤8：reduce阶段，对每一个对象对所在的区域内进行扫描，如果能够找到以key为直径的对象集合，则作为候选的输出结果；取距离最小的前十个候选对象进行序列化，输出到对应的文件中。

进一步地，所述两点配对法具体如下：

集合空间关键字查询的目标是查找位置最接近的若干个对象的集合，其中接近的度量方式采用对象集合的“直径”描述，即使用对象集合中两两距离的最大值作为直径；集合关键字查询就是去查找能够包含所有关键字，并且直径最小的对象集合；

首先将对象进行两两组合形成对象对，然后将对象对按距离大小进行升序排列，最后逐一将对象对扩展为对象集合，如果某一个对象对可以被扩展为对象集合，那么该对象集合即为所求结果。

进一步地，所述叶子节点对角线剪枝方法具体如下：

Hilbert R-树的构建采用的是自底向上的方式，首先是生成叶子节点，叶子节点是使用最小外包矩形作为它的空间属性；如果一个叶子节点中包含了所有查询关键字，那么能够在这个叶子节点中找到一个满足所有查询关键字的对象集合，且它的直径小于这个叶子节点的对角线距离，所以该叶子节点的对角线距离即是集合空间关键字查询的结果的上限；

在Hilbert R-树生成的时候，对生成的叶子节点进行判定，如果包含所有查询关键字，那么该叶子节点的对角线距离即为结果的上限，之后随着叶子节点的生成，更新该上限值，当所有叶子节点生成完，满足该条件的最小叶子节点的对角线距离即为最小上限；采用这个最小上限作为阈值。

本发明的有益效果如下：

1.针对集合空间关键字查询的实用化问题，提出了基于空间大数据的查询策略，丰富了基于地图的位置服务。

2.设计了利用Hilbert R-树空间搜索的查询算法：以两点配对方式为基础、加入了叶子节点对角线剪枝和圆扫描剪枝过程，有效地降低了检索空间的遍历；

3.完成了算法在MapReduce并行环境下的具体实现方法和步骤，实验证明该算法可以将查询相关数据读入内存，完成大规模数据情况下的集合关键字查询能力；

4.实验结果表示所提出查询策略可以有效地降低时间开销：证实了在MapReduce环境下Hilbert R-树空间搜索算法对于关键字搜索效率的显著提高。

附图说明

图1是本发明所提出的MapReduce环境下的查询算法对于不同机器数量和不同关键字数量的检索时间对比。

图2是本发明两点配对算法的扫描区域示意图。

图3是本发明叶子节点对角线剪枝方法示意图。

图4是本发明圆扫描剪枝方法示意图。

图5是本发明所提出查询算法的流程图；

图6是本发明验证所提出的剪枝方式的有效性验证结果对比。

具体实施方式

下面结合附图和实施例对本发明进一步说明。

本发明针对地图应用的集合空间关键词查询问题，以MapReduce计算框架为基础，提出了一种在大数据的环境下的集合关键字查询策略，采用Hilbert R-树作为索引，并使用基于两点配对的组合方式，可以有效地提高查询系统响应速度。使用MapReduce完成基于大数据环境的空间集合查询算法的设计和实现，基于实际地图位置查询应用。除此之外，本发明所涉及的算法可以应用于与位置、社交媒体数据分析和位置敏感的业务运营有关的问题,它在个人活动，公司活动和城市运营中起着重要作用,具有较好的应用前景。

本发明的核心思想分为两点：一是在面向地图应用的海量数据的情况下，由于内存有限，无法将所有数据直接读入内存中，但是实际检索的关键字相关的数据量仅仅是整体数据的极小部分，可以在内存中仅对这一小部分数据进行实时索引的建立，并且利用该索引与高效的查询算法完成查询工作。二是提出在并行框架Hadoop环境下的两点配对算法，并设计了相应的剪枝规则，可以在集群机器下完成检索空间的压缩与剪枝，提高了查询速度。

本发明设计了一种基于Hilbert R-树的空间数据查询算法：以两点配对方式为基础、加入了叶子节点对角线剪枝和圆扫描剪枝过程。

1.两点配对法

两点配对法基本思想：集合空间关键字查询的目标是查找位置最为“相近”的若干个对象的集合，其中“相近”的度量方式采用对象集合的“直径”来描述，即使用对象集合中两两距离的最大值作为直径，一个对象集合的直径越大，说明集合的对象间的距离相距较远，集合关键字查询就是去查找能够包含所有关键字，并且直径最小的对象集合。解决集合关键字查询的本质是比较不同的对象集合的直径，由于对象集合的数量为指数级增长，本发明采用两点配对算法完成对象集合的查找过程，首先将对象进行两两组合形成“对象对”，然后将“对象对”进行升序排列，最后逐一将“对象对”扩展为“对象集合”，如果某一个对象对可以被扩展为对象集合，那么该对象集合即为所求结果。借助于树形空间索引，这种方式可以将原本需要指数级列举的节点集合变为多项式级别，避免了节点列举过程中爆炸式增长带来的查询延迟。

在将“对象对”扩展为一个“对象集合”时，作为后补的对象点会集中在对象对附近的区域中，如图2阴影部分所示，即以A，B为圆心的，|AB|(A,B之间的距离)为半径的两个圆所重合的区域，这样可以保证区域内的对象与A或B的距离不大于|AB|。在算法中，首先确定该区域是否包含所有查询关键字，其次进行对象的组合，这里只需要对区域的对象进行组合，相比于整体的查询对象，可以极大的减少对象组合的开销。

2.叶子节点对角线剪枝与圆扫描剪枝

叶子节点对角线剪枝的基本思想：Hilbert R-树的构建采用的是自底向上的方式，首先是生成叶子节点，节点是使用最小外包矩形作为它的空间属性。如果一个节点中包含了所有查询关键字，那么一定可以在这个节点中找到一个满足所有关键字的对象集合，且它的直径小于这个节点的对角线距离，所以该节点的对角线距离即是集合空间关键字查询的结果的上限。如图3所示，一个叶子节点的矩形包含了四个对象A、B、C、D，且A、B、C、D包含了所有的查询关键字，那么dis(A,C)即这个对角线的距离是对象集合{A,B,C,D}的直径，它小于或等于矩形的对角线距离。

这样一来，可以Hilbert R-树生成的时候，对生成的叶子节点进行判定，如果包含所有关键字，那么该叶子节点的对角线距离即为结果的上限，之后随着叶子节点的生成，更新该上限值，当所有叶子节点生成完，满足该条件的最小叶子节点的对角线距离即为最小上限。利用这个最小上限作为阈值，生成对象对的时候，所有的对象对必须要小于这个阈值，这样可以有效地减少对象对的生成，并且节省了内存开销。

圆扫描剪枝基本思想是在叶子节点对角线剪枝规则的基础上，进一步为对单个对象的判定,当有不满足的对象点时,直接将这个对象从内存中删除。

在图4中，相交的部分是前文中的提到的由“对象对”生成“对象集合”所查找的区域，假设MN为需要判定的“对象对”，且最小对象集合的在阴影部分存在，那么可以断定，该对象集合的直径小于

3.基于MapReduce框架的算法具体步骤图5所示。

在Hadoop分布式框架下，利用MapReduce框架设计本发明的具体查询步骤。对象数据的格式包含：1)数据所包含的关键字；2)数据的经纬度坐标。所有数据是存放在HDFS中。

1)：Mapper类中，从HDFS的block读取数据，数据读取过程中，根据对象的关键字，将符合查询条件的点放内存中，并根据查询关键字生成该数据的keyBit。keyBit是表示数据包含关键字的二进制代码。然后序列化HilbertCurve对象，根据对象的经纬度坐标求出其hilbert value，建立Hilbert R-树，并将Hilbert R-树传给所有的计算节点。

2)：生成叶子节点，判断叶子节点所包含的关键字，如果包含所有关键字，那么这个节点的对角线距离就是阈值。

3)：重复步骤2)，如果某个叶子节点满足所有的关键字，且对角线距离小于阈值，则更新阈值为该对角线距离，直到所有的叶子节点全部生成完。

4)：遍历所有对象o，将

5)：遍历点，进行剩余对象的两两配对。

6)：运用Hilbert R树，在Hilbert R树中判断点对的区域内是否包含所查询的所有关键字。

7)：点对距离作为key，两个点对象作为value输出给reduce。

8)：reduce阶段，对每一个对象对所在的区域内进行扫描，如果可以找到以为直径的对象集合，则作为候选的输出结果。取前十个候选对象进行序列化，如果输出到对应的文件中。

具体实施例：

为了证明本发明的有效性，进行了实验结果的对比：实验数据是一个以关键字命名的文本文件，每一行包含一个数据点，该数据点有三个属性，id，x坐标，y坐标。设定了195678组数据，设定376个关键字。

如图1。应用本发明所提出的算法，分别在关键字数量为3、4、5的情况下，比较了不同机器数下的运行时间，明显可以看到，随着机器数量的增加，运行时间越来越小，呈线性减小，由此说明，在分布式环境下的搜索效率远远高于单机的搜索效率，所以将Hilbert R-树空间搜索算法放在MapReduce环境下会显著体改其搜索效率。

此外，为了验证两种剪枝方法的有效性，将使用叶子节点对角线剪枝与圆扫描剪枝的方式与不使用这两种剪枝方式的运行结果进行比较。实验在MapReduce环境下，使用三台机器运行，通过比较不同的关键字数量和运行时间的关系，验证两种剪枝算法的有效性。如图6可以明显的看到加入剪枝方式的方法在搜索相同关键字数量的情况下运行时间有一定的提高。