本发明属于关键词查询技术领域，更具体地，涉及一种基于摘要图的空间rdf数据关键词查询方法。
背景技术：
目前的万维网能够方便、即时地访问大量在线信息。然而，web中的内容通常是供人使用的，而不是为机器处理而设计的。所以，网络上的内容只是人可读，而计算机是无法理解和处理的。计算机只能看到文本和图像，并不理解其中的意义。比如，我们能够轻松理解网页内容，但是计算机只知道这是一个网页，网页中的图片是关于什么的，网页中的超链接指向的页面和当前页面有何关系，这些计算机都不清楚。为了使计算机能够理解并处理网页内容，语义网(semanticweb)的概念应运而生。语义网正是为了使网络上的数据变得机器可读而提出的一个通用框架，“semantic”表示用更丰富的方式表达数据背后的含义，“web”表示将这些数据相互连接，组成一个庞大的信息网络。语义网在万维网之上加入了一些可以被计算机“理解”的语义信息，它在方便人们阅读和使用的同时，也方便计算机之间的相互交流与合作。
语义网的快速发展使得语义数据大量增加，对语义数据的检索也成为了当下的研究热点。据统计，目前可免费获取的语义数据集已超过3000个，约有1500亿个三元组，其中大多数是以rdf、rdfs、owl语言描述的。这些由本体语言描述、以三元组(主语，谓词，宾语)形式组织起来的数据称为语义网数据(也称rdf数据)。主语和宾语用结点表示，谓词用有向边表示，有向边由主语指向宾语。随着rdf(resourcedescriptionframework，资源描述框架)数据的大量增加，普通用户对其进行查询的需求也在不断增加。目前已经有一些查询语言如sparql、serql等支持rdf数据查询，但它们对普通用户而言过于复杂，原因在于其要求用户必须掌握查询语言的语法规则和待查询数据的模式信息。因此，rdf数据的关键词查询模型成为了当下学术界与工业界的研究热点。
目前最先进的rdf数据空间关键词查询方法是2016年提出的空间rdf数据top-k相关语义位置检索算法(top-kkeywordqueryalgorithmforspatialrdfdata，sk算法)，该算法将rdf数据的空间查询和关键词查询结合在了一起，这既满足了空间查询的需求，又能够为普通用户提供一个简单友好的关键词查询接口。由于大多数空间结点无法到达所有的关键词，这些空间结点构造结果子图时会遍历完所有的rdf数据，所以该算法在大规模数据上效率较低。
技术实现要素：
针对现有技术的缺陷，本发明的目的在于解决现有技术sk算法在输入数据过大的情况下，查询效率会明显降低的技术问题。
为实现上述目的，第一方面，本发明实施例提供了一种基于摘要图的空间rdf数据关键词查询方法，该方法包括以下步骤：
步骤s1.基于类型属性划分原rdf图，得到划分子图的集合p，基于类型间的关系将集合p中不同的图结构提取出来，得到摘要图集合s；
步骤s2.利用摘要图集合以逆向搜索的方式在划分子集合p上进行关键词查询，生成包含所有关键词的子图集合；
步骤s3.将子图集合作为空间rdf数据的关键词top-k搜索算法的输入，得到最终的查询结果。
具体地，按照结点的类型属性划分原rdf图，得到划分子图集合p，包括以下子步骤：
s111.找出原rdf图中所有结点的类型属性；
s112.针对每个类型属性，找出具备该属性的实体结点；
s113.针对每个实体结点，以bfs方式、搜索半径为r遍历原rdf图，生成对应的子图h，所有子图h构成划分子图集合p，划分集合p中的元素间是边互斥的；
s114.为每个划分子图建立连接点索引，所述连接点索引是由划分子图到其包含的所有连接点集合的映射表。
具体地，半径r的取值范围为[1，3]。
具体地，所述将集合p中不同的图结构提取出来，得到摘要图集合s，包括以下步骤：
s121.判断所有划分子图是否遍历完，若是，进入步骤s124，否则，计算当前遍历到的划分子图hi的核；
s122.将c与当前摘要图集合s中各摘要图s依次进行同态比较，若c同态于s，则记录同态映射，并用hi+1更新hi，进入步骤s121；若s同态于c，则记录同态映射，并将s从摘要图集合s移除；
s123.将c添加到摘要图集合s中，则用hi+1更新hi，进入步骤s121；
s124.根据记录的同态映射，为划分子图中每个结点生成摘要索引，所述摘要索引将该结点映射到摘要图中的对应结点。
具体地，在步骤s121中，每遍历到一个划分子图，为该划分子图h(v，r)生成一个类型树ht(v，r)，并用类型树替代h(v，r)，所述类型树ht(v，r)的生成方式具体如下：从点v出发，以bfs的方式遍历h(v，r)，每访问一个结点u，就生成一个与结点u类型相同的新结点，该新结点只包含类型信息。
具体地，步骤s1还包括：为所有的空间结点建立了r-tree索引，为每个结点生成了一个描述文档，并且为这些描述文档建立倒排索引。
具体地，步骤s2包括以下步骤：
(1)根据倒排索引初始化关键词结点集合w1，w2，…，wm，初始化各优先队列
(2)遍历各关键词结点集合wi中的各结点，根据摘要索引获取当前遍历到的结点u所属的划分子图h(v，r)，如果m[v]不存在，则为m[v]创建m个空列表，并且将
(3)将优先队列a1，a2，…，am中dl值最小的(v，(u，path，dl))取出，根据连接点索引，获取划分子图h(v，r)的所有连接点集合l＝{l′1，l′2，…}，获取path中最后一个元素(l，vl)；
(4)遍历连接点集合l，计算连接点l到当前遍历到的连接点l′的距离下界d′l，当前相连的划分子图的中心结点为vnext，如果将l′添加到path后形成了环，则遍历下一个连接点；否则，将t＝(u，path∪(l′，v)，dl+d′l)添加到m[vnext]的第i个列表中，将(vnext，t)添加到优先队列ai中，遍历新增t与其他m-1个队列中三元组中所组成的不同子图，判断当前遍历到的子图g的松散度下界是否满足
(5)遍历连接点集合l完成，判断是否达到终止条件，若是，输出所有生成的子图g构成的子图集合，否则，进入步骤(3)。
具体地，所述距离下界的计算方式如下：
(1)根据摘要索引计算d(v，v1)和d(v，v2)，进一步计算dl(v1，v2)＝|d(v，v1)-d(v，v2)|，其中，v1和v2为中心结点v对应的划分子图h(v，r)中的结点，d()表示两个结点之间的距离，dl()表示两结点之间的距离下界；
(2)不同划分子图的两个结点的最短距离下界dl(u1，u2)＝从u1到，u2经过的每个划分子图的入口结点到出口结点的dl(v1，v2)之和。
具体地，终止条件为：
第二方面，本发明实施例提供了一种计算机可读存储介质，该计算机可读存储介质上存储有计算机程序，该计算机程序被处理器执行时实现上述第一方面所述的基于摘要图的空间rdf数据关键词查询方法。
总体而言，通过本发明所构思的以上技术方案与现有技术相比，具有以下有益效果：
1.本发明在sk算法的基础上进行优化，添加了摘要搜索层。该算法首先生成划分子图集合和摘要图集合，然后在利用摘要图集合在划分子图集合上进行逆向搜索，即从关键词结点出发，自底向上进行搜索，得到若干包含所有关键词的子图。然后将这些子图作为输入，进行空间rdf数据top-k关键词的查询。因为划分子图的数量远小于结点数量，从而缩小查询范围，且利用摘要图能够很快得到路径长度下界，整个算法的查询效率明显提升。
2.本发明引入了类型树对生成摘要算法进行了优化，不同结构的划分子图对应于相同的类型树，所以引入类型树可以减少摘要图集合s的规模。这样更利于将摘要图集合存储在内存中，也提高了查询的效率。并且，对树进行同态判断比对图进行同态判断更简单。
附图说明
图1为本发明实施例提供的一种基于摘要图的空间rdf数据关键词查询方法流程图；
图2为本发明实施例提供的原rdf图；
图3为本发明实施例提供的映射记录示例图；
图4为本发明实施例提供的sks算法伪代码图。
具体实施方式
为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。
如图1所示，一种基于摘要图的空间rdf数据关键词查询方法，该方法包括以下步骤：
步骤s1.基于类型属性划分原rdf图，得到划分子图的集合p，基于类型间的关系将集合p中不同的图结构提取出来，得到摘要图集合s。
原rdf图数据是一个六元组：g＝(v，lv，fv，e，le，fe)，其中，
(1)v＝vc∪ve∪vl，v是顶点集合，对应于rdf数据中的所有主语(subject)和宾语(object)，vc、ve、vl分别代表类型结点、实体结点和字面量结点。
(2)lv是结点标签集合。
(3)fv：v→lv为点-标签函数，是一个双射函数，fv使得顶点与标签一一映射。给定顶点u∈v，若u∈vl，则顶点u的标签为u的字面量；若u∈vc∪ve，则顶点u的标签为u的uri。
(4)e是有向边的集合，由主语指向宾语。
(5)le是边的标签的集合。
(6)fe：e→le为边-标签函数，是一个双射函数。fe使得边与标签一一映射。给定一条边e∈e，则边e的标签为e的谓词。
如图2所示，截取自dbpedia的真实rdf图数据。图中有三种结点，白方框表示实体结点ve，灰方框表示类型结点vc，剩下是字面量结点vl。
步骤s11.按照结点的类型属性划分原rdf图，得到划分子图集合p。
s111.找出原rdf图中所有结点的类型属性。
如图2所示，找到了person、spatialthing、architecture三种类型属性。
s112.针对每个类型属性，找出具备该属性的实体结点。
如图2所示，具备person属性的实体结点有anne_of_denmark和elizabeth；具备spatialthing属性的实体结点有hampton_court_palace和westminster_abbey；具备architecture属性的实体结点有baroque和gothic。
s113.针对每个实体结点，以bfs方式、搜索半径为r遍历原rdf图，生成对应的子图h，所有子图h构成划分子图集合p。
从当前遍历结点出发，以bfs(广度优先遍历)的方式生成半径不大于r的子图。设由结点v出发生成的子图为h(v，r)。生成的子图间是边互斥的，所以以bfs的方式访问并添加边之前，需判断该边是否被添加到了别的划分子图中，若是，则不将该边添加到h(v，r)中；否则，将该边添加到h(v，r)中。搜索半径r取值范围为[1，3]。
从h(v，r)生成过程中可以看出，各个结点到中心结点v的距离为1至r。因为划分子图间边互斥，所以可能会出现h(v，r)中只有v结点，没有任何边的情况。将h(v，r)添加到划分集合p中。遍历所有结点后，返回划分集合p。由划分集合的性质可知，划分集合p中的元素间是边互斥的，且所有元素取并集后等于完整的rdf图。
s114.为每个划分子图建立连接点索引，所述连接点索引是由划分子图到其包含的所有连接点集合的映射表。
因为划分子图间是边互斥，结点可重复的，所以存在一些结点会出现在不同的划分子图中，将这些划分子图连接起来。本发明将这些连接不同划分子图的结点称为连接点，用l表示。连接点索引可表示为：h(v，r)→{l1，l2，…}，其中，集合{l1，l2，…}为划分子图h(v，r)包含的所有连接点。
步骤s12.将集合p中不同的图结构提取出来，得到摘要图集合s。
本发明基于类型间的关系来构建摘要，保留了不同类型的实体间所有连接信息，不需要模式信息，摘要图生成一次就行。将划分子图间的不同结构提取出来，这涉及到判断两图是否相同，或者一张图是否包含于另一张图的问题，这些问题等同于图同态问题。
s121.判断所有划分子图是否遍历完，若是，进入步骤s124，否则，计算当前遍历到的划分子图hi的核c。
图c是图g的核，当且仅当
(1)存在一个图同态满足f1：c→g；
(2)存在一个图同态满足f2：g→c；
(3)图c是是满足性质(1)、(2)的所有图中的最小图，即结点最少。
s122.将c与当前摘要图集合s中各摘要图s依次进行同态比较，若c同态于s，则记录同态映射，并用hi+1更新hi，进入步骤s121；若s同态于c，则记录同态映射，并将s从摘要图集合s移除。
若c同态于s，表示c的结构包含于s中；若s同态于c，表示s的结构包含于c中。一个由图g＝(v，e)到图g′＝(v′，e′)的图同态记为：f∶g→g′，可读作g同态于g′，当且仅当
(1)f是一个结点映射函数，即f：v→v′；
(2)f(x)＝x表示结点f(x)与结点x的类型相同；
(3)若(u，v)∈e，则(f(u)，f(v))∈e′，且边(u，v)与边(f(u)，f(v))的类型相同。
s123.将c添加到摘要图集合s中，则用hi+1更新hi，进入步骤s121。
s124.根据记录的同态映射，为划分子图中每个结点生成摘要索引，所述摘要索引将该结点映射到摘要图中的对应结点。
如图3所示，带箭头的实线是映射记录log中记录的映射关系。带箭头的虚线表示该划分子图到摘要的最终映射关系。可以看到，一个划分子图要么是摘要图集合s中的某一个元素，要么同态于另一个划分子图。当摘要图集合s生成完毕后，可以从映射记录中找到每个ht到摘要的映射关系。
摘要索引可表示为：u→(h(v，r)，s，snode)，其中，划分子图h(v，r)中结点u对应于摘要图s中的结点snode。或者，表示为：u→(v，sid，hid)，其中，v表示结点u所属划分子图h(v，r)的中心结点，结点u对应于编号为sid的摘要图中、编号为hid的结点。
考虑到同态判断是一个np完全性问题，算法效率低，为了解决这一问题，本发明引入了类型树，对生成摘要算法进行了优化。不同结构的划分子图对应于相同的类型树，所以引入类型树可以减少摘要图集合s的规模。这样更利于将摘要图集合存储在内存中，也提高了查询的效率。并且，对树进行同态判断比对图进行同态判断更简单。
优选地，在步骤s121中，每遍历到一个划分子图，为该划分子图h(v，r)生成一个类型树ht(v，r)，并用类型树替代h(v，r)。类型树ht(v，r)的生成方式具体如下：从点v出发，以bfs的方式遍历h(v，r)，每访问一个结点u，就生成一个与结点u类型相同的新结点，该新结点只包含类型信息。
在预处理阶段，为所有的空间结点(带有空间信息的实体，如类型为spatialthing的结点)建立了r-tree索引，目的是为了能够快速找到下一个需要构建候选结果的空间结点。为每个结点生成了一个描述文档，并且为这些描述文档建立倒排索引，目的是为了查询过程中能够快速找到包含关键词的结点。在初始化阶段，ks算法将根据输入的查询关键词，利用倒排索引生成一个结点-关键词映射表mq，ψ，该映射表的key是结点，value是该结点中包含的关键词list，即mq，ψ的key值都是包含关键词的结点，value值也都是关键词。因为通常用户输入的关键词个数较少，所以mq，ψ的构建速度非常快，占用空间也小。利用mq，ψ能够在进行bfs搜索时快速判断当前结点是否包含关键词，从而提高查询效率。
步骤s2.利用摘要图集合以逆向搜索的方式在划分子集合p上进行关键词查询，生成包含所有关键词的子图集合。
查询输入是一个三元组：q＝(λ，ψ，k)，其中，λ是查询坐标，ψ＝fw1，w2，…，wm}是查询关键词集合，k是需要返回的答案个数。
遍历所有划分子图，以逆向搜索的方式在划分子图上进行关键词查询，将与关键词不相关的部分裁剪掉，生成若干子图，每个子图都包含了所有的关键词。因为划分子图的数量远小于结点数量，从而缩小查询范围，且利用摘要图能够很快得到路径长度下界，所以第一层搜索效率较高。
该搜索层将划分子图看作遍历的基本单位，采用逆向搜索的思路，从各个包含关键词的划分子图出发，以bfs的方式遍历划分子图，若m个(用户输入的查询关键词个数)包含不同关键词的划分子图，到达了同一个划分子图，则将这些划分子图及其经过的划分子图连接起来，生成一个新的子图g，子图g包含了所有关键词，然后将子图g作为第二层搜索的输入。
如图4所示，具体步骤如下：
(1)根据倒排索引初始化关键词结点集合w1，w2，…，wm，初始化各优先队列
优先队列用于获取逆向搜索的访问顺序。优先队列中每个元素都是一条起点为关键词结点出发的路径，即优先队列ai记录了当前以包含关键词wi的结点为起点的所有路径，其形式为(v，(u，path，d1))，其中，v为路径终点，u为路径起点，path记录了路径上经过的所有划分子图及之间的出口和入口，dl为该路径最短长度的下界。优先队列采用最小堆实现，且以路径长度下界dl的大小进行排序。m中记录了所有访问路径，且是按路径终点分类存储的，m[v]表示终点划分子图为h(v，r)的所有访问路径，记录表m用于判断是否有新的子图g生成。
(2)遍历各关键词结点集合wi中的各结点，根据摘要索引获取当前遍历到的结点u所属的划分子图h(v，r)，如果m[v]不存在，则为m[v]创建m个空列表，并且将
将划分子图h(v，r)添加到访问路径记录表m后，更新记录表m和优先队列ai。
(3)将优先队列a1，a2，…，am中dl值最小的(v，(u，path，d1))取出，根据连接点索引，获取划分子图h(v，r)的所有连接点集合l＝{l′1，l′2，…}，获取path中最后一个元素(l，vl)。
划分子图h(v，r)是该路径最后经过的划分子图，路径path记录了该路径是由连接点l进入到h(v，r)中。
(4)遍历连接点集合l，计算连接点l到当前遍历到的连接点l′的距离下界d′l，当前相连的划分子图的中心结点为vnext，如果将l′添加到path后形成了环，则遍历下一个连接点；否则，将t＝(u，path∪(l′，v)，dl+d′l)添加到m[vnext]的第i个列表中，将(vnext，t)添加到优先队列ai中，遍历新增t与其他m-1个队列中三元组中所组成的不同子图，判断当前遍历到的子图g的松散度下界是否满足
路径长度的估算
(1)根据摘要索引计算d(v，v1)和d(v，v2)，进一步计算dl(v1，v2)＝|d(v，v1)-d(v，v2)|，其中，v1和v2为中心结点v对应的划分子图h(v，r)中的结点，d()表示两个结点之间的距离，dl()表示两结点之间的距离下界。
使用摘要索引能够很快计算出一个划分子图h(v，r)中，由中心结点到任意结点的距离。可以利用三角不等式计估算出，划分子图中任意两个结点间的最短距离取值范围。如对h(v，r)中的两个结点v1和v2，可以估算出距离下界为：d(v1，v2)≥|d(v，v1)-d(v，v2)|。
(2)不同划分子图的两个结点的最短距离下界dl(u1，u2)＝从u1到，u2经过的每个划分子图的入口结点到出口结点的dl(v1，v2)之和。
对属于不同划分子图的两个结点u1和u2的距离估算，也可以使用三角不等式，因为从u1到u2会经过若干个划分子图，这些划分子图是通过连接点串起来的，如每个经过的子图都有一个入口，一个出口。入口到出口的距离可以由上述三角不等式估算出下界，然后将经过的子图距离的下界累加起来，即可获得d(u1，u2)的取值范围。
(5)遍历连接点集合l完成，判断是否达到终止条件，若是，输出所有生成的子图g构成的子图集合，否则，进入步骤(3)。
终止条件
判断是否终止搜索算法，等同于判断是否可能会出现优于最优解队列hk中元素的解。这个潜在最优解可能会出现在(1)未访问的划分子图中，也可能会出现在(2)已访问的划分子图中。接下来分别分析这两种情况的潜在解的松散度下界。
对于第一种情况，设优先队列ai的队首元素为
对于第二种情况，设路径记录表m中包含不同关键词且路径长度最短的路径为
综上所述，终止条件为：
其中，rmax是当前第k个最优解的排序函数值，α为松散度的权重参数。
排序函数值r(tp，q)＝α×l(tp)+(1-α)×s(q，p)
其中，r(t，q)为在候选结果子图t中查询输入q的代价，l(tp)为候选结果子图的松散度；s(q，p)为查询坐标q.λ到候选结果中心结点p的距离；α为松散度的权重参数。结果子图中每个关键词到中心结点的距离之和为子图松散度。松散度越低，子图越紧凑，越符合最佳答案。本发明中α默认为0.5。
步骤s3.将子图集合作为空间rdf数据的关键词top-k搜索算法的输入，得到最终的查询结果。
第二层(数据层搜索)将会以bfs的方式进行空间关键词查询。具体地，每次从未访问的空间结点中获取离查询坐标最近的空间结点(按r-tree索引的顺序获取)。由该空间结点出发，以广度优先遍历(bfs)的方式搜索关键词。若搜索到了所有的关键词，则生成候选结果，并且对该候选结果进行排序，输出top-k个最优解。
给定一个rdf图数据g＝(v，e)一个查询q＝(λ，ψ，k)，查询结果是一个包含k个元素三元组集合：aq＝{t1，t2，…，tk}。当且仅当
1.
点击拨打：