◎黄高昂

大规模图数据中紧密子结构查询系统设计

◎黄高昂

查询广泛应用在大数据及图形数据的查询，如信息网络，SOC及知识图等，由于缺乏结构支持,一次关键词查询可能会产生过多的结果匹配,一个重要但是容易忽略的任务是将这些查询结果中具有相似结构或者内容的部分进行总结,如通过向后拓展搜索，双向扩展搜索，闪烁算法等，可以便于更好地解释查询和理解查询结果。

关键词查询在查询图式数据(社交网络,知识图谱,信息网络)有着广泛的运用,图式数据上的查询是将图中与查询的关键词相关的数据进行提取,关键词查询解释程序通过对于关键词在图中提取到的结果图来将一次关键词查询转换为图结构的查询。关键词查询可能会含混不清，图查询准确度更高，把关键字和图数据查询结合起来，可以得到查询效率度准确度更高的查询。

质量测量(Quality Measurement)

前提假设结果图集包含一次关键词查询中的所有关键词。给定一个关键词对(ki,kj)(ki,kj∈Q ki≠kj) 和由关键词查询Q产生的结果图集G。

如果任意在G中的连接关键词vki和vkj的路径p都能在Gs中找到一条拥有与路径p

相同标签的连接vsi和vsj的路径ps(vki∈[vsi],vkj∈[vsj]),称总结图Gs覆盖了(ki,kj)。

引入概念—覆盖率：

给定一次关键词查询和由此产生的结果图集G,定义结果图集的总结图的覆盖率α为α = 2M / |Q|(|Q| - 1)。

M是Gs所覆盖的关键词对(k,k’)的总数.注意关键词查询Q总共的关键词对的数量为|Q|(|Q|-1) 。

把对于由Q产生的结果图集的覆盖率为α总结图 称为 α-Summary Graph。

基于覆盖率的质量测量更倾向于包含更多关键词对的结果图。

引入概念—总结尺寸 定义一个总结图的尺寸为总结图中所含有的全部结点和边的数量总结图越小,该图的简洁性越好，两个测量标准结合到一起。

定义：Gs是一个最小的α-summary graph。

含义：对于任意其他的α-summary graph Gs’ |Gs|≤ |Gs’|。

优势关系(Dominance relation) 在结果图G=(V,E,L)上的一对关键词(k,k’)的优势关系是在G上中间点的一种二元关系,以至于任意属于关系R≤(k,k’)的结点对(v1,v2),有L(v1) = L(v2);对于任意一条在关键词k的结点vk1和关键词k’的结点之间且通过结点v1的路径p1,必存在一条与p1有相同的标签且通过结点v2连接关键词k的结点vk1’和关键词k’的结点vk2’路径p2.我们称对于关键词对(k,k’)v2优势关系于v1。

图1 Psum算法

XRANK

概述：与传统的HTML关键词查询不同，XML的关键词查询返回的是包含所请求关键词的深层嵌套的XML元素，而不是返回整个文件。关键词查找是在信息检索中最有效的范例之一。其中最主要的原因之一是它的简单性,用户不用掌握一门复杂的查询语言,而且可以不需要知晓数据的存储结构就能进行查询,XRANK保留简单的关键词查询接口,仍在查询过程中利用XML的标签和嵌套结构，我们将一组具有超链接的XML文件集定义为一个有向图G=(N,CE,HE) 结点集合N=NE∪NV，其中NE是XML元素的集合,NV是XML值的集合(元素标签名和属性名也作为XML值) CE是结点之间包含关系的边的集合,明确地说,当且仅当v是u的子元素称边(u,v)∈CE。HE是结点之间包含超链接关系的边的集合,当且仅当u包含一个指向v的超链接则称边(u,v)∈HE。(v,u)∈CE：元素u是元素v的子元素 (u,v)∈CE：元素u是元素v的双亲当结点v直接或间接包含关键词k时 定义谓词＊(v,k)为真假定包含n的关键词的一次关键词查询Q={k1,k2,k3,..,kn} 令R0={v|v∈NE∧任意k∈Q(contains＊(v,k))}为直接或间接包含查询中全部关键词的元素集合,则查询Q的结果定义为 ：

排列函数定义：假定ElemRank(v)是通过XML文件中基础超链接的结构计算出的元素v的客观重要性,与Google的PageRank算法很相似,不同在于ElemRank是定义在元素的粒度上,并且将XML的嵌套结构加入考量。令一次关键词查询Q=(k1,k2,k3,…,kn)和它对应的结果R=Result(Q),其中一个结果元素v1(v1∈R) 在定义v1全局的rank值,rank(v1,Q)之前,先定义关于关键词ki的v1的rank值。

关 键 词ki的v1的rank值： 对于每一个关键词ki,存在一个v1的子元素或属性值v2,满足v2 R0而且contains＊(v2,ki).

在CE中存在一个包含边的序列(v1,v2),(v2,v3),…,(v_t,v_t+1)满 足 v_t+1是一个直接包含关键词ki的结点

直观地看出,关于ki的v1的rank值是ElemRank(v_t)进行适当地缩放来表明结果的明确性。

decay是一个可以被设置为范围在0到1直接的值。

上述定义中,我们隠式地假设了关键词ki在v1中只出现一次.如果出现m次,我们首先用上述公式计算每次出现的rank值.设计算出的rank值为r1,r2,r3,…,rm最终组合起来的rank值为

这里f是聚集函数.我们默认设置f=max。

总rank值定义：关于查询Q=(k1,k2,…,kn)查询结果元素v1的总rank值为

其中Ne为XML所有元素的总数,Nc(u)是元素u的子元素的个数,E=HE∪CE∪CE^-1,其中CE^-1是包含边集的反转集,这个公式没有将包含边和超链接边所区分开来,举一个例子,假设一个含有少部分的包含边和大量的引用,那么会造成对于每个部分的包含边会有更少的价值,我们对其进行进一步的改进,将包含边和超链接边区分开来

本系统是基于Psum算法和Xrank算法，意在让实验者理解，掌握Psum和Xrank的工作原理和工作过程中各个部分的功能。结构较为简单，过程不很复杂，但是实验精度会受到一定限度，以后应着力提高该实验的精度。需要说明的是，由于该系统为演示实验，工作平面无需太大，一台电脑可以完成。

（作者单位：武汉大学 计算机学院）