一种空间索引的建立方法、使用方法及装置

摘要

本发明公开了一种空间索引的建立方法、使用方法及装置，使用分类数据库中设定的类别对空间数据库中的空间对象进行分类；针对每一类空间对象，根据此类空间对象在空间区域内的分布，使用四叉树方式不断划分空间区域，直至划分后的每个子区域内的此类空间对象的分布满足设定的条件；使用R树方式对划分后的每个子区域内的此类空间对象建立空间索引。本发明通过对各类空间对象建立空间索引，能够降低由于各类空间对象相互重叠的几率，并且由于在对每类空间对象建立空间索引时，依据各类空间对象分布特征，将空间对象分布密集的空间区域划分成更小的区域，进一步降低了出现空间重叠的几率，从而提高了使用建立的空间索引进搜索的速度和精度。

说明书

技术领域

本发明涉及数据业务领域，尤其涉及一种空间索引的建立方法、使用方法 及装置。

背景技术

随着互联网的普及和信息技术的迅速发展，人们对各种信息，特别是地理 信息的依赖越来越大。据统计，现在人们80％以上的活动都和空间位置相关， 因此，如何从海量的地理信息数据中准确、迅速的找到自己所需的信息，成为 当前迫切需要解决的问题。

目前，对地理信息的查询技术主要包括以下步骤：接收用户查询请求信息 后，对查询请求信息进行分词，获取有效地址和关键词；查询预置数据库，获 取该有效地址的空间几何信息，确定待搜索空间区域；在待搜索空间区域内， 以该关键词进行搜索，最后输出搜索结果。在此过程中，会使用空间索引来加 快搜索速度，那么什么是空间索引呢？

空间索引是指依据空间对象的位置和形状或空间对象之间的某种空间关 系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象 的标识、外接矩形及指向空间对象实体的指针。作为一种辅助性的空间数据结 构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特 定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率。

空间对象一般具有二维特性，例如空间对象为地图上的一条道路，一个湖 泊，一个宾馆时，对应的二维特性为一个点、一条线或一个面，使用空间索引 技术能够根据搜索条件，迅速地查找到所需的空间对象。例如：需要查找与一 个矩形框相交的所有空间对象的集合，当全图的数据量巨大，矩形框相对于全 图很小时，这个集合相对于全图数据集大为缩小，在这个缩小的集合上再处理 各种复杂的搜索，效率就会大大提高。

一般地，空间索引技术包括：网格索引、四叉树索引、R树和QR树等。 其中，QR树是指定深度为N的四叉树将整个索引空间分成2的N次方个空 间，四叉树的每个结点均与一索引子空间和一棵R树相关联，QR树也可以看 作是一群R树的集合，这些R树分别索引不同空间的目标实体。QR树结合了 四叉树与R树的优势，与R树相比，QR树以略大(有时甚至略小)的空间开 销代价，换取了更高的性能，且索引目标数越多，QR树的整体性能越好。

但是，在实际使用QR树建立空间索引时，在现实世界实际的划分情况比 假设的情况复杂很多倍，特别是在城市中多个空间对象的数据相互叠加在一起 的情况很常见，这样会出现空间索引文件过大或树深度过大，并且会出现大量 的空间重叠问题和“死空间(不包含搜索目标的索引空间)”，这些都会极大地 影响检索速度和效率。

发明内容

本发明实施例提供了一种空间索引的建立方法、使用方法及装置，用以解 决现有的空间索引技术在空间对象分布复杂且不均的情况下，出现空间重叠 导致搜索速度慢精度低的问题。

本发明实施例提供的一种空间索引的建立方法，包括：

使用分类数据库中设定的类别对空间数据库中的空间对象进行分类；

针对每一类空间对象，根据此类空间对象在空间区域内的分布，使用四叉 树方式不断划分所述空间区域，直至划分后的每个子区域内的此类空间对象的 分布满足设定的条件；

使用R树方式对划分后的每个子区域内的此类空间对象建立空间索引。

本发明实施例提供的一种使用上述方法建立的空间索引的使用方法，包 括：

对接收到的查询请求进行文本分词，获取关键词；

使用分类数据库中设定的类别对所述关键词进行分类，得到所述关键词所 属的类别；

使用地址数据库获取所述关键词对应的地理区域范围；

通过遍历所述关键词所属的类别对应的空间数据库的空间索引，进行查找 所述关键词对应的地理区域范围所涉及的子区域；

输出所述关键词对应的地理区域范围所涉及的子区域中的所有空间对象 的信息。

本发明实施例提供的一种空间索引的建立装置，包括：

分类单元，用于使用分类数据库中设定的类别对空间数据库中的空间对象 进行分类；

划分单元，用于针对每一类空间对象，根据此类空间对象在空间区域内的 分布，使用四叉树方式不断划分所述空间区域，直至划分后的每个子区域内的 此类空间对象的分布满足设定的条件；

空间索引建立单元，用于使用R树方式对划分后的每个子区域内的此类空 间对象建立空间索引。

本发明实施例提供的一种使用上述装置建立的空间索引的使用装置，包 括：

分词模块，用于对接收到的查询请求进行文本分词，获取关键词；

分类模块，用于使用分类数据库中设定的类别对所述关键词进行分类，得 到所述关键词所属的类别；

地址获取模块，用于使用地址数据库获取所述关键词对应的地理区域范 围；

搜索模块，用于通过遍历所述关键词所属的类别对应的空间数据库的空间 索引，进行查找所述关键词对应的地理区域范围所涉及的子区域；

输出模块，用于输出所述关键词对应的地理区域范围所涉及的子区域中的 所有空间对象的信息。

本发明实施例的有益效果包括：

本发明实施例提供的一种空间索引建立方法、使用方法及装置，使用分类 数据库中设定的类别对空间数据库中的空间对象进行分类；针对每一类空间对 象，根据此类空间对象在空间区域内的分布，使用四叉树方式不断划分空间区 域，直至划分后的每个子区域内的此类空间对象的分布满足设定的条件；使用 R树方式对划分后的每个子区域内的此类空间对象建立空间索引。本发明通过 对空间对象的分类，针对各类空间对象建立空间索引，能够降低由于各类空间 对象相互重叠的几率，并且由于在对每类空间对象建立空间索引时，依据各类 空间对象分布特征，将空间对象分布密集的空间区域划分成更小的区域，进一 步降低了出现空间重叠的几率，从而提高了使用建立的空间索引进搜索的速度 和精度。

附图说明

图1为本发明实施例提供的空间索引的建立方法的流程图；

图2为本发明实施例提供的空间区域划分的示意图；

图3为本发明实施例提供的密度阈值测定方法的流程图；

图4为本发明实施例提供的空间索引的使用方法的流程图；

图5为本发明实施例提供的空间索引的建立装置的结构示意图；

图6为本发明实施例提供的空间索引的使用装置的结构示意图。

具体实施方式

下面结合附图，对本发明实施例提供的空间索引的建立方法、使用方法及 装置的具体实施方式进行详细地说明。

本发明实施例提供的一种空间索引的建立方法，如图1所示，具体包括以 下步骤：

S101、使用分类数据库中设定的类别对空间数据库中的空间对象进行分 类；

S102、针对每一类空间对象，根据此类空间对象在空间区域内的分布，使 用四叉树方式不断划分空间区域，直至划分后的每个子区域内的此类空间对象 的分布满足设定的条件；

S103、使用R树方式对划分后的每个子区域内的此类空间对象建立空间索 引。

其中，在步骤S102中使用的四叉树方式和步骤S103中使用的R树方式划 分空间区域都属于现有技术，在此不再赘述。

下面对上述各步骤的具体实现方式进行详细的说明。

具体地，在上述步骤S101使用分类数据库中设定的类别对空间数据库中 的空间对象进行分类，可以通过下述方式实现：

判断分类数据库中是否存在与空间对象的属性对应的类别；

若存在，将空间对象归属到类别中；

若不存在，将空间对象归属到使用神经网络的分类算法计算出的最接近的 类别中，确保每个空间对象都有归属类别，其中，使用的神经网络的分类算法 属于现有技术，在此不再说明。

具体地，在上述步骤S101中使用的分类数据库的分类数据来源可以包括 两个部分，其一：可以通过基础地图数据和兴趣点(POI，Point ofInterest)数 据做数据归类，得到具体的分类数据，例如哪些是行政区域、宾馆和餐馆等； 其二：可以通过互联网抓取海量网页中的数据、垂直网站中的内容数据和地图 运营商的数据等，之后经过数据去重、去无关信息等，最后将数据归类得到具 体地分类数据。

经过步骤S101后，在空间数据库中复杂的空间对象被归属到各自的类别 中，之后针对每类空间对象建立空间索引，能够降低各类空间对象之间相互重 叠的几率，极大降低了空间重叠问题，从而提高了使用建立的空间索引进行搜 索的速度和精度。

具体地，本发明实施例提供的上述方法中的步骤S102，可以通过下述步骤 实现：

使用四叉树方式不断划分空间区域，计算每次划分后的各子区域的空间对 象密度；

当确定本次划分后的子区域的空间对象密度不大于设定的密度阈值时，停 止使用四叉树方式划分本次划分后的子区域。

例如：如图2所示，当判断出划分后的子区域B的空间对象密度小于设定 的密度阈值0.7时，就可以停止使用四叉树方式对子区域B的划分，然后使用 R树方式在子区域B中建立空间索引；当判断出划分后的子区域C的空间对象 密度大于设定的密度阈值0.7时，需要继续使用四叉树方式对子区域C划分， 得到子区域C1、C2、C3和C4，然后分别计算子区域C1、C2、C3和C4的空 间对象密度，与设定的密度阈值0.7比较，确定子区域C1、C2、C3和C4的 空间对象密度均小于于密度阈值0.7后，使用R树方式分别在子区域C1、C2、 C3和C4中建立空间索引。

具体地，上述步骤S102，也可以通过下述方式实现：

使用四叉树方式不断划分空间区域，计算每次划分后的各子区域的空间对 象密度和四叉树的深度；

当确定本次划分后的子区域的空间对象密度不大于设定的密度阈值或本 次划分后四叉树的深度达到设定的第一深度阈值时，停止使用四叉树方式划分 本次划分后的子区域。

例如：如图2所示，当判断出子区域A的空间对象密度小于设定的密度阈 值0.7时，但四叉树的深度1没有到达第一深度阈值3，停止使用四叉树方式 对子区域A的划分，然后使用R树方式在子区域A中建立空间索引；当判断 出划分后的子区域C1、C2、C3和C4的空间对象密度大于设定的密度阈值0.7 时，但四叉树的深度3已达到了第一深度阈值3，停止使用四叉树方式划分子 区域C1、C2、C3和C4，使用R树方式分别在子区域C1、C2、C3和C4中建 立空间索引。

其中，对空间区域进行划分时，依据了空间对象密度进行判别是否需要划 分区域，空间对象密度表征了空间对象的区域分布特征，从空间对象密度可以 了解到某个区域内的空间对象分布的稀疏程度，例如通过考察一个城市内不同 区域中的商业网点分布，就可以知道哪个区域是该城市的商业中心。如果在某 个区域内的空间对象的分布比较密集，就需要对此区域再次划分，减少空间对 象的重叠现象。

较佳地，可以根据实际的空间区域中空间对象的分布情况，增加对四叉树 深度的判断，比如如果四叉树深度大于5层时，直接在该子区域内使用R树方 式构建空间索引，不在判断空间对象密度是否小于密度阈值，这样可以避免发 生子区域的空间对象密度一直不能小于设定的密度阈值时，不断使用四叉树方 式划分，产生死循环的情况。

优选地，在上述步骤S102的两个具体实现过程中，各子区域的空间对象 密度具体地可以使用下述公式计算获得：

D＝∑MBR_i/S；

其中，MBR_i为本次划分后的子区域内的第i个空间对象的最小边界矩形的 面积；S为使用四叉树方式对空间区域第一次划分后的子区域的面积。

由于上述公式中的S不会随着空间区域划分的深入而变化，相对恒定，因 此能够保证空间对象密度随着空间区域不断划分而逐渐收敛。

此外，上述空间对象密度的计算公式只是原理公式，上述公式的各种变型 公式也可以计算出空间对象密度，在此不再一一赘述。

在上述步骤S102中使用的密度阈值，可以根据不同空间区域中的一类空 间对象的分布情况，设置不同的密度阈值，密度阈值可以根据经验值来确定， 确保四叉树方式和R树方式的深度在合理的范围内。

优选地，密度阈值也可以通过下述的迭代法进行测定，如图3所示，包括 以下步骤：

S301、设置初始密度阈值，一般地，初始密度阈值可以是一块空间区域的 所有空间对象密度的均值；

S302、使用四叉树方式不断划分空间区域，直至所有子区域的空间对象密 度均不大于初始密度阈值时，计算四叉树的深度；

S303、判断四叉树的深度是否小于设定的第二深度阈值，例如5，如果是， 执行步骤S304；如果否，执行步骤S305；

S304、确定密度阈值为初始密度阈值；

S305、调整初始密度阈值，可以在初始密度阈值上增加步长例如0.1，返 回步骤S302～S303。

上述使用迭代法测定密度阈值只是确定密度阈值的一种实施方式，还可以 使用例如空间聚类法等技术实现密度阈值的确定，在此不做限定。

使用本发明实施例提供的上述空间索引建立方法建立的空间索引，充分体 现了使用四叉树方式划分空间区域的划分简单、可控分辨率和查找速度快的优 点，也体现了使用R树方式划分空间区域的检索效率高、检索精度高的优点， 并且避免了使用R树方式划分空间区域的平衡和分裂比较复杂、更新速度慢和 重建空间索引慢的缺点。

本发明实施例还提供了一种使用上述方法建立的空间索引的使用方法，如 图4所示，具体包括以下步骤：

S401、对接收到的查询请求进行文本分词，获取关键词；

S402、使用分类数据库中设定的类别对关键词进行分类，得到关键词所属 的类别；

S403、使用地址数据库获取关键词对应的地理区域范围；

S404、通过遍历关键词所属的类别对应的空间数据库的空间索引，进行查 找关键词对应的地理区域范围所涉及的子区域；

S405、输出关键词对应的地理区域范围所涉及的子区域中的所有空间对象 的信息。

下面通过一个具体地实例对上述空间索引的使用方法进行说明。

例如：用户输入查询：“马甸桥附近的住宿”，在接收到次查询请求后，对 此请求进行文本分词，获取关键词“马甸桥”和“宾馆”；使用分类数据库对 关键词“马甸桥”进行分类得到“北京市地区”，对关键词“住宿”进行分类 得到“宾馆”；使用地址数据库获取“马甸桥”对应的地理区域坐标；在北京 市区域的宾馆类的空间索引内查找与“马甸桥”的地理区域坐标涉及的空间索 引的子区域，包括包含“马甸桥”的地址区域坐标的子区域和与“马甸桥”的 地址区域相交的子区域；输出这些子区域内的宾馆的信息。

基于同一发明构思，本发明实施例还提供了一种空间索引的建立装置和使 用装置，由于该装置解决问题的原理与前述一种空间索引的建立方法和使用方 法相似，因此该装置的实施可以参见方法的实施，重复之处不再赘述。

本发明实施例提供的一种空间索引的建立装置，如图5所示，包括：

分类单元501，用于使用分类数据库中设定的类别对空间数据库中的空间 对象进行分类；

划分单元502，用于针对每一类空间对象，根据此类空间对象在空间区域 内的分布，使用四叉树方式不断划分空间区域，直至划分后的每个子区域内的 此类空间对象的分布满足设定的条件；

空间索引建立单元503，使用R树方式对划分后的每个子区域内的此类空 间对象建立空间索引。

进一步地，本发明实施例提供的上述装置中的分类单元501，具体用于判 断分类数据库中是否存在与空间对象的属性对应的类别；若存在，将空间对象 归属到类别中；若不存在，将空间对象归属到使用神经网络的分类算法计算出 的最接近的类别中。

进一步地，本发明实施例提供的上述装置中的划分单元502，具体用于使 用四叉树方式不断划分空间区域，计算每次划分后的各子区域的空间对象密 度；当确定本次划分后的子区域的空间对象密度不大于设定的密度阈值时，停 止使用四叉树方式划分本次划分后的子区域。

或者，进一步地，本发明实施例提供的上述装置中的划分单元502，具体 用于使用四叉树方式不断划分空间区域，计算每次划分后的各子区域的空间对 象密度和四叉树的深度；当确定本次划分后的子区域的空间对象密度不大于设 定的密度阈值或本次划分后四叉树的深度达到设定的第一深度阈值时，停止使 用四叉树方式划分本次划分后的子区域。

进一步地，本发明实施例提供的上述装置中的划分单元502，具体用于通 过下述公式计算每个子区域的空间对象密度D：D＝∑MBR_i/S；其中，MBR_i为 本次划分后的子区域内的第i个空间对象的最小边界矩形的面积；S为使用四 叉树方式对空间区域第一次划分后的子区域的面积。

进一步地，本发明实施例提供的上述装置，如图5所示，还可以包括：密 度阈值单元504，用于设置初始密度阈值；使用四叉树方式不断划分空间区域， 直至所有子区域的空间对象密度均不大于初始密度阈值时，计算四叉树的深 度；判断四叉树的深度是否小于设定的第二深度阈值，如果是，确定密度阈值 为初始密度阈值；如果否，调整初始密度阈值，对空间区域重新进行划分，直 至划分后的所有子区域的空间对象密度均不大于调整后的初始密度阈值且四 叉树的深度小于第二深度阈值，确定密度阈值为调整后的初始密度阈值。

本发明实施例还提供了一种使用上述装置建立的空间索引的使用装置，如 图6所示，包括：

分词模块601，用于对接收到的查询请求进行文本分词，获取关键词；

分类模块602，用于使用分类数据库中设定的类别对关键词进行分类，得 到关键词所属的类别；

地址获取模块603，用于使用地址数据库获取关键词对应的地理区域范围；

搜索模块604，用于通过遍历关键词所属的类别对应的空间数据库的空间 索引，进行查找关键词对应的地理区域范围所涉及的子区域；

输出模块605，用于输出关键词对应的地理区域范围所涉及的子区域中的 所有空间对象的信息。

通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到本发明 实施例可以通过硬件实现，也可以借助软件加必要的通用硬件平台的方式来实 现。基于这样的理解，本发明实施例的技术方案可以以软件产品的形式体现出 来，该软件产品可以存储在一个非易失性存储介质(可以是CD-ROM，U盘， 移动硬盘等)中，包括若干指令用以使得一台计算机设备(可以是个人计算机， 服务器，或者网络设备等)执行本发明各个实施例所述的方法。

本领域技术人员可以理解附图只是一个优选实施例的示意图，附图中的模 块或流程并不一定是实施本发明实施例所必须的。

本领域技术人员可以理解实施例中的装置中的模块可以按照实施例描述 进行分布于实施例的装置中，也可以进行相应变化位于不同于本实施例的一个 或多个装置中。上述实施例的模块可以合并为一个模块，也可以进一步拆分成 多个子模块。

上述本发明实施例序号仅仅为了描述，不代表实施例的优劣。

本发明实施例提供的一种空间索引建立方法、使用方法及装置，使用分类 数据库中设定的类别对空间数据库中的空间对象进行分类；针对每一类空间对 象，根据此类空间对象在空间区域内的分布，使用四叉树方式不断划分空间区 域，直至划分后的每个子区域内的此类空间对象的分布满足设定的条件；使用 R树方式对划分后的每个子区域内的此类空间对象建立空间索引。本发明通过 对空间对象的分类，针对各类空间对象建立空间索引，能够降低由于各类空间 对象相互重叠的几率，并且由于在对每类空间对象建立空间索引时，依据各类 空间对象分布特征，将空间对象分布密集的空间区域划分成更小的区域，进一 步降低了出现空间重叠的几率，从而提高了使用建立的空间索引进搜索的速度 和精度。

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发 明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及 其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。