基于RDF图的Skyline高效检索算法设计

首先，该篇博客使用的数据集是yago，首先阐述下数据集共有三个文件，分别存放每个顶点关键词、顶点之间的连接关系和地点p集合。高效检索算法的起点是若干顶点关键词，过程是在RDF图中寻找较为合适的地点（各个关键词都可达，并且不被任何其他地点支配），终点是返回不被其他地点支配的地点，也就是skyline point，下面简称为SP。

相信不了解问题背景的小伙伴应该对于RDF图和语义地点支配关系应该并不熟悉，因此，下一部分由小编给大家做下背景知识介绍。

由于算法较为复杂，这篇博客只对关键部分进行阐述，不详细阐述算法有关的原理和定理，想要深入了解这部分内容可以到小编主页的资源页面下载相应的论文和高效检索算法实现的源码。

第一章 RDF图和语义地点支配

1、RDF图

下面图1为一个RDF图的实例，图中p点为语义地点1；v点为一般顶点，不作为检索结果返回；两个顶点间可达在图1中体现为存在连接两点的路径。图2为顶点的文本信息，也就是每个顶点所含有的关键词。

2、语义距离

由图2中可知，v3中含有art，p3也含有art，因此，p1到art这个关键词有两条路，分别为

D(p1,v3)=3,D(p1,p3)=1；

语义距离是p点到关键词的最小距离，因此，这里取语义距离

T(p1,art)=1;

3、语义支配

承接第2部分的例子，由于T(p3,art)=0<T(p1,art)=1；因此，存在如下关系：p3就关键词art支配p1这个点，因此返回结果，应该舍弃p3。

所以，这里的语义支配关系其实是一种多元组的偏序关系，也就是若某地点p到达所有关键词的语义距离都小于等于另一个地点q，那么可以认为q支配p，记为p<q（这里用小于符号表示，严格来说应该用偏序的符号表示）。

4、检索实例

在图1中，给定一组查询关键词 O{sculpture, art, history}，图 1所示的RDF图 ，其中顶点的文本属性如图 2所示，其中 和 是两个相关语义地点。在这两个语义地点中，关键词到两个根节点的距离分别是d_g (T_(p_1 ),sculpture)=3，d_g (T_(p_1 ),art)=1，d_g (T_(p_1 ),history)=3，d_g (T_(p_2 ),sculpture)=1，d_g (T_(p_2 ),art)=1 ，d_g (T_(p_2 ),history)=2 。根据语义地点支配的定义，可以看出 支配 ，因为存在一些关键字 ，这些关键词在 中的距离小于在 中的距离，并且所有关键字在 中的距离都小于等于在 中的距离，这样就可以记为 。那么语义地点skyline查询 O{sculpture, art, history}的结果是 T_p2.

第二章 BNL算法实现

BNL算法用于语义距离已经计算好后，通过比较返回不配其他任何地点支配的SP点。

1、算法描述

BNL算法又称为块嵌套环算法，是最早、也是最简单的一种无索引的Skyline查询算法。这种算法的主要思想是首先开辟一个内存空间作为窗口，每次读取新的疑似SP的点与窗口中已经存在的点进行比较，剔除窗口中被支配的算法，并判断新的点是否有可能是SP（不被当前窗口中的任何一点支配的点），若是将其加入窗口中，反之舍弃该点，直至所有p点被遍历结束后，依然留在窗口中的p点即为所求的SP。

值得注意的是，在数据集十分大的情况下，可以在执行过程中将窗口中的疑似SP的点的信息保留在临时文件中，这样可以防止窗口满了后新的点不能加入。后面操作需要时把临时文件中的点再与窗口中的点进行合并，才可得到真正的SP。

2、算法步骤

假设p点到各个关键词的语义距离都已经通过穷举或者其他算法计算得到了。

Step1：将第一个p点装入窗口中（vector容器）；

Step2：读取下一个p点，判断其与窗口中的点的支配关系，一般会有如下两种情况以及处理：

Stituation1：窗口中存在一点q，使得p<q，即q支配p，那么p必然不可能是要求的SP，所以在与q比较后立即舍弃p；

Stituation2：p点支配窗口中1个或多个点，那么这些被p支配的点也不可能是SP，因此，将它们都从窗口中删掉，由于偏序关系具有传递性，因此，可以断定窗口中不可能有任何的点支配p点，因此，需要将p点作为疑似SP点加入到窗口中。

Step3：重复Step2直至读取完最后一点后，窗口中剩下的点就是本次查询的SP。

3、算法实现伪代码

4、算法复杂度分析及评价

这里小编直接把自己论文里面详细的分析过程截图放上来。

5、读者须知

由于计算语义距离的耗时远远超过BNL算法返回SP的耗时（一般成1：10~100的情况），所以设计高效检索算法时，BNL算法作为最后阶段的算法，并且耗时少，所以高效检索的核心不在于BNL算法，而在于用最快的速度计算出所有p点的语义距离。

高效检索算法的设计

相信很多小伙伴应该可以发现，大部分情况下，计算语义距离是整个问题最为耗时的部分，因此，这篇博客的高效检索算法就是通过图的BFS遍历性质设计出高效计算语义距离的算法和BNL算法结合得到的检索算法。

1、高效检索算法的大致流程

这里小编先给出高效检索算法的工作流程图，给大家先有个直观的印象；

2、B-树结构引入

这里涉及到的B-树结构实现参考这篇博客：B-树结构C语言实现

B-树结构实现较复杂，过程较多，无法做过多描述，需要大家自行查阅，还请小伙伴们见谅。

通过截图引用小编论文的原话和伪代码讲述我对B-树结构做出的修改：

3、高效检索算法的设计与实现

这里小编决定直接给出算法实现流程和伪代码，关于算法可行性和原理分析这块的话，请麻烦小伙伴到我的主页上查找小编上传的资源，里面有关于该算法详细的论文（20页）和源码实现。由于算法较为复杂，因此，小编建议还是要看论文后再去尝试源码。

（1）算法实现步骤

假设查询K个的关键词的SP，检索算法步骤

Step0：按照BFS遍历正向图访问结点顺序向B-Tree插入对应结点的关键词，直到BFS遍历结束，所有的结点的关键词都插入到B-Tree后，建树完毕。

Step1：已经建好的B-Tree中查找关键词key_i，得到具有该关键词的结点链表nolist_i;

（注意：基于Step0，所以此时nolist_i中结点的顺序是按照反向图中层次的降序。）

Step2：以nolist_i链表中的顶点为根节点，利用反向邻接表进行BFS遍历，每次遍历时不重置访问标志变量visited数组。当遍历到的顶点刚好是p点时，则gap[p][i]为当前的层数。

（注意：此步是高阶检索之于低阶检索重要区分。）

Step3：重复Step1和Step2直到K个关键词查找完毕。

Step4：通过上述步骤，所有p点的语义距离均计算完毕，因此，在这里依旧使用上文提到的BNL算法进行筛选，选出此次查询的SP。

（2）算法实现伪代码

实验结果

在论文里有更为详细的实验结果，这里只给出大家最为关心的检索时间方面的结果。注意：这些实验数据纯随机，无任何人为挑选的因素。