许多现实应用中,图数据的规模都在不断地扩大.Facebook在2012年4月公布其月活跃用户人数(顶点数)达到9亿,好友关系(边数)达到1 250亿.在这样规模的图上进行查询,将是非常耗时的.

在社交网络等图数据上,人们通常关心两个顶点(例如社交网络中的人)之间是否存在一条长度小于等于k的路径,这种查询被称为k可达查询.对于有向图G=(V,E),k可达查询就是查询给定顶点u和v的最短距离是否不超过k.例如在图 1(a)中,给定查询“顶点v₁和v₈是否2可达”,通过计算可知,顶点v₁和v₈的最短距离为3,所以查询结果为“否”.

在k可达查询处理方面已经开展了一些研究工作:

1) 对于固定的k值,文献^[1]中提出了一种基于建立h步顶点覆盖索引的k可达查询处理算法,可以对外存上的图数据进行k可达查询处理,但是这种方法只能回答特定k值下的k可达查询,对于非特定的k值则需要建立一组索引;

2) 图上的可达查询已经有了广泛的研究^[2-4],文献^[5]中也做出了较为详细的综述.因为可达查询是k可达查询的一种特例,即,k为¥的情况,所以已有的可达查询处理算法不能适用于k可达查询;

3) 距离查询是k可达查询的一种扩展形式,可以通过Dijkstra算法实现.因为大图上的查询往往是很耗时的^[6],所以文献[7-9]中都是通过建立有效的索引来实现快速的查询处理.但是,随着图规模的扩大,索引的大小也会迅速增大而无法适用.

本文用图压缩以及压缩图上直接进行查询处理的技术来解决k可达问题,其思想如下:首先,将图G进行压缩,得到一个规模很小的压缩图G_R;然后,对于任意G上的k可达查询Q,将Q转换成G_R上的等价查询Q¢,使得Q(G)=Q¢(G_R),即,在G上对Q的查询结果与在G_R上对Q¢的查询结果完全相同.由于G_R的规模远小于G的规模,故可以大幅提高查询处理效率,并节省存储空间.

文献[10-13]中提出了支持可达性查询的图压缩算法,其中,文献[11-13]提出了基于传递闭包的压缩算法:将原始图G=(V,E)压缩为G_t=(V,E_t),满足E_tÎE,且对于任意的顶点u和v,u与v在G中存在一条路径当且仅当u与v在G_t中存在一条路径;文献^[10]则通过将具有相同祖先和后继的顶点{u₁,u₂,…,u_l}压缩为一个等价类[u]_R,实现了对原始图的有效压缩.由于上述压缩算法仅能保留顶点之间是否可达的信息而丢失了距离信息,因此无法适用于k可达查询.这是因为:

1) 可达查询只是k可达查询的一种特殊形式,即k值为¥的情况;

2) 在可达查询中往往并不关心顶点之间的最短距离,因此距离信息会被丢失;而在k可达查询中,任意两个顶点u和v之间最短距离的缺失都可能会导致查询结果的不正确.

本文首先提出了图压缩算法k-RPC以及压缩图G_R=(V_R,E_R)上无需解压缩的k可达查询处理算法,其时间复杂度分别为O(|E|log|V|)和O(|V_R|+|E_R|).本文证明了k-RPC算法是所有支持k可达查询的基于等价类的图压缩算法中最优的,即,任何一个基于等价类且支持k可达查询的图压缩算法得到的压缩图都不会比k-RPC算法得到的压缩图更小.通过实验验证:k-RPC算法可以将稀疏的原始图压缩掉55%,将稠密的原始图压缩掉25%;与在原始图上直接进行查询处理相比,基于压缩图的查询处理在稀疏图上的效率可以提高2.5倍.

由于k-RPC是基于比较严格的等价关系,当原始图比较稠密时,该等价关系将变得不易满足.此时,可以通过删除原始图G中的一些边以使G变得稀疏,然后使用k-RPC进行压缩.由于删除的边集E⁺将会影响到压缩图的大小,故,本文提出了最优边集问题来计算使压缩图最小的E^*.本文进一步证明了最优边集问题是NP-hard的,并提出了线性的近似算法k-GRPC以及压缩图上无需解压缩的k可达查询处理算法.k-GRPC算法的时间复杂度为O(|E|log|V|+s|E_R|),查询处理算法的时间复杂度为.通过实验验证:k-GRPC算法可以将稀疏的原始图压缩掉55%,将稠密的原始图压缩掉33%;与在原始图上直接进行查询处理相比,基于压缩图的查询处理在稀疏图上的效率也可以提高2.5倍.

本文的主要工作及贡献如下:

(1) 提出了一种支持k可达查询的图压缩算法k-RPC以及压缩图上无需解压缩的查询处理算法,证明了其正确性,在稀疏图和稠密图上的压缩比分别可达到45%和75%,稀疏图上的查询效率可提高2.5倍;

(2) 证明了k-RPC在支持k可达查询的基于等价类的图压缩算法中是最优的;

(3) 提出了最优边集问题并证明了该问题是NP-hard的;

(4) 提出了线性的近似图压缩算法k-GRPC以及压缩图上无需解压缩的k可达查询处理算法,进一步将在稀疏图和稠密图上的压缩比提高到45%和67%,稀疏图上的查询效率可提高2.5倍.

1 相关工作

在大图上的k可达查询处理已经有了一些相关的研究^{[6, 7, 8, 9, 14]}.已有的针对距离查询的算法都是通过建立有效的索引来实现快速的查询处理,即采用了“空间换时间”的策略,其中,文献^{[6, 8]}提出的2-hop label通过建立O(|V|×|E|^1/2)的索引,可以在O(|H|/n)内完成查询处理,其中,|H|表示了索引的大小;TEDI^[7]通过O(n²)的时间构造了O(l|R|²)的树结构索引,可以在O(tw²h)内完成查询处理,其中,tw表示了树的宽度,h表示了树的高度.但是随着图规模的扩大,这些方法建立索引的大小也会迅速增大而无法适用.

文献^[1]中,针对k可达查询提出了一种基于建立h步顶点覆盖索引的方法,可以较为有效地建立索引并完成查询,但是这种方法建立的索引只能用来回答特定k值下的k可达查询.

支持可达查询的图压缩技术已被提出^[10-13],其中,文献[11-13]提出了基于传递闭包的图压缩方法,可以在保留可达信息的同时删除原始图中大量的边;文献^[10]通过将具有相同祖先和后继的顶点归为一个等价类,从而实现对原始图更加有效的压缩.但是因为可达查询并不关心顶点之间的最短距离,所以这些方法不能适用于k可达查询.

2 基于图压缩的查询处理算法

本文针对有向无权图进行研究,给定图G=(V,E),对于顶点uÎV,vÎV,(u,v)和(v,u)是不同的两条边.尽管有向边通常也使用áu,vñ表示,在不引起歧义时,本文仍使用(u,v)表述.由于自环(u,u)不影响G上的k可达查询,因此可以从G中删除,故,本文仅考虑不带有自环的有向图.

对于任意的顶点uÎV,father(u)={w|(w,u)ÎE},child(u)={w|(u,w)ÎE},本文使用的有向图采用邻接表的形式存储,且所有顶点的邻居都是按顺序存储的.文中使用d(G,u,v)表示G中顶点u和v之间的最短距离.下面给出图G顶点集合V上等价关系“º”的定义.

定义1. 给定图G=(V,E),“º”是V上的二元关系,对于顶点uÎV,vÎV,uºv当且仅当father(u)=father(v)且child(u)=child(v).

易知,关系“º”满足自反性、对称性和传递性,所以关系“º”是V上的等价关系.可以根据“º”将V划分为若干个等价类,[u]_R={x|xÎV,uºx}表示包含顶点u的等价类.

2.1 图压缩算法k-RPC及查询算法

本文首先给出一种图压缩方法k-RPC:将图G中的顶点划分为若干个等价类,每个等价类都是压缩图G_R=(V_R,E_R)中的一个顶点;压缩图G_R中两个顶点[u]_R和[v]_R之间存在一条边([u]_R,[v]_R)当且仅当在原始图G中存在两个顶点u_iÎ[u]_R和v_jÎ[v]_R,满足(u_i,v_j)ÎE.算法1给出了k-RPC的具体执行过程.

Algorithm 1. k-RPC.

Input: Graph G=(V,E);

Output: Compressed Graph G_R=(V_R,E_R).

① for each node u do

② [u]_R={u};

③ end for

④ sort all uÎV according to u’s neighbors;

//对顶点排序

⑤ CF=CC=CV=Æ, V_R=E_R=Æ;

//CF,CC和CV分别表示当前父亲集合、儿子集合和等价类

⑥ for each ordered uÎV do //计算所有等价类

⑦ If father(u)=CFÙchild(u)=CC then

⑧ [CV]_R=[CV]_RÈu, [u]_R=Æ;

⑨ else

⑩ V_R=V_RÈ[CV]_R;

⑪ CF=father(u), CC=child(u), CV=u;

⑫ end if

⑬ end for

⑭ For each vertex pair [u]_RÎV_R, [v]_RÎV_R do

//计算压缩图的边集

⑮ if(u,v)ÎE then

⑯ E_R=E_RÈ([u]_R,[v]_R);

⑰ end if

⑱ end for

⑲ return G_R=(V_R,E_R);

在将G压缩为G_R后,可以在压缩图G_R上直接进行k可达查询.对于任意给定的G上的两个顶点u和v,为了判断u和v在G中是否k可达,可以通过判断[u]_R和[v]_R在G_R中是否k可达而给出结果.我们使用了广度优先算法来查询压缩图上任意两个顶点之间的最短距离.

例如,在对图 1(a)所示的原始图G进行压缩时,因为顶点v₂和v₄具有相同的父亲{v₁}和儿子{v₃,v₆,v₇},所以将合并v₂和v₄得到图 1(b)所示的压缩图G_R.而对于给定查询“顶点v₄和v₈是否3可达”,根据压缩图G_R,可以找到一条路径[v₄]_R®[v₃]_R®[v₅]_R®[v₈]_R,故将给出查询结果“是”,这与在原始图G上的查询结果是相同的.

以下定理将证明在压缩图G_R上进行k可达查询的结果是正确的.

引理1. 在压缩图G_R=(V_R,E_R)中,[u]_RÎV_R,[v]_RÎV_R,那么([u]_R,[v]_R)ÎE_R当且仅当对于任意顶点u_iÎ[u]_R,v_jÎ[v]_R,均有(u_i,v_j)ÎE.

证明:由k-RPC计算压缩图G_R的方法,充分性显然.下面证明必要性.

若([u]_R,[v]_R)ÎE_R,则存在顶点u₀Î[u]_R,v₀Î[v]_R,使得(u₀,v₀)ÎE.

因为等价类[u]_R中任意两个顶点的儿子完全相同,所以对于任意顶点u_iÎ[u]_R,均有(u_i,v₀)ÎE.

又因为等价类[v]_R中任意两个顶点的父亲完全相同,所以对于任意顶点u_iÎ[u]_R,v_jÎ[v]_R,均有(u_i,v_j)ÎE.

证毕.

定理1. 给定有向图G=(V,E),G_R=(V_R,E_R)是通过k-RPC算法得到的压缩图,则G中任意两个顶点u和v满足d(G_R,[u]_R,[v]_R)=d(G,u,v).

证明:假设d(G,u,v)=d,即,在G中顶点u可以通过路径P:u®w₁®w₂®…®w_d-1®v到达顶点v.如果对于路径P上任意两个顶点w_i和w_j都有[w_i]_R¹[w_j]_R,那么,P¢:[u]_R®[w₁]_R®[w₂]_R®…®[w_d-1]_R®[v]_R是一条连接顶点u和v的长度为d的简单路径;否则,P上存在两个顶点w_i和w_j,使得[w_i]_R=[w_j]_R.于是我们有:顶点w_i和w_j的儿子完全相同.不妨假设i<j,那么顶点u可以通过路径u®w₁®…®w_i®w_j+1®…®w_d-1®v到达顶点v.这说明P并不是连接顶点u和v的最短路径,矛盾.因此在G_R中,顶点[u]_R也一定可以通过一条长度为d的简单路径P¢到达顶点[v]_R.

下面来说明在G_R中,P¢是连接顶点[u]_R和[v]_R的最短路径.假设G_R中存在一条连接顶点[u]_R和[v]_R的路径P²: [u]_R®[x₁]_R®[x₂]_R®…®[x_p]_R®[v]_R满足p<d,那么,分别从[x₁]_R,[x₂]_R,…,[x_p]_R对应的顶点集合里任意选择1个顶点y₁,y₂,…,y_p.根据引理1可知:对于任意0<i<p,(y_i,y_i+1)ÎE,(u,y₁)ÎE且(y_p,v)ÎE,因此,在G中找到了一条连接顶点u和v的长度为p的简单路径u®y₁®y₂®…®y_p®v.矛盾.

综上所述,我们有d(G_R,[u]_R,[v]_R)=d(G,u,v).

下面分析k-RPC算法的复杂度.

因为k-RPC算法将判断每一对顶点u和v是否等价,根据顶点等价的定义,算法将依次访问顶点u和v的邻居.由于本文使用的有向图是采用邻接表形式存储的,且已经有序,故,判断顶点u和v是否等价的时间复杂度为O(deg(u)+deg(v)).由于算法需要考察所有的顶点对,为了提高效率,算法将首先对顶点进行排序,如算法第4行所示.排序的规则是:根据顶点的邻居id,以类似字典序的方法从小到大排列.例如,在图 1(a)中,顶点v₂的邻居是{v₁,v₃,v₆,v₇},顶点v₃的邻居是{v₁,v₂,v₄,v₅},那么,v₃将排在v₂之前.容易发现,在排序后等价的顶点一定是连续排列的.因为在比较代价为O(1)时,排序的复杂度为O(|V|log|V|),而算法需要比较顶点的所有邻居,故,此时比较代价为O(deg(u)),所以排序的复杂度为O(|V|log|V|×avg(deg(u)))=O(|E|log|V|).在算法第6行~第13行,算法完成了对所有等价类的划分,此时需要访问一遍所有顶点的邻居,其代价为O(|E|);在算法的第14行~第18行,算法完成了压缩图边集合的构造,易知其代价为O(|E|).综上所述,k-RPC图压缩算法的复杂度为O(|E|log|V|).因为查询处理转化时需要计算顶点归属的等价类,我们可以在算法1的执行过程中记录下等价类划分的映射关系,所以查询处理转化的代价为O(1),故,使用广度优先算法进行k可达查询处理的代价为O(|V_R|+|E_R|).

综上所述,使用k-RPC算法有两个优点:

1) 可以实现对原始图G的有效压缩,从而节省大量的存储空间;

2) 可以在压缩图G_R上直接进行查询而无需进行解压缩,从而将查询处理的时间从O(|V|+|E|)降低为O(|V_R|+|E_R|).

事实上,根据定理1,原始图上任意两个顶点u和v之间的距离均与其在压缩图上对应的等价类[u]_R和[v]_R之间的距离相等.因此,可以用压缩图作为输入,使用已有的建立索引的方法^[6-9]进一步提高查询速度.由于本文的主要目标在于如何通过压缩实现有效的查询,故,查询处理采用了最为直观的广度优先算法.

当原始图发生了动态更新时,可以对压缩图做出相应的更新.图上可能的更新共有3种:孤立顶点的插入/删除、边的插入、边的删除.下面分别讨论3种情况下的更新操作:1) 容易发现,孤立顶点的插入/删除不会影响压缩图中其余等价类的划分,如果压缩图中存在由孤立点组成的等价类,那么可以直接通过向该等价类中插入或从该等价类中删除顶点来实现上述更新;2) 当发生边的插入或者删除时,边两端顶点u和v的邻居都会发生改变,因此需要更新顶点u和v的排序.通过二分法,上述排序可在O(log|V|×avg(deg(u)))内完成.排序后,可以在常数时间内重新划分顶点u和v所属的等价类.

k-RPC算法同样适用于无向图,因此也可以解决许多无向图上的问题.在枚举极大团^[15]、枚举三角形^[16]等诸多应用中,均可使用k-RPC算法压缩原始图,并且能够无需解压缩地完成查询处理.

2.2k-RPC最优性分析

k-RPC算法采用了基于等价类的压缩思想,即,从原始图G中找到属于同一“类”的顶点并将其压缩为G_R中的一个顶点,因此,对于“类”的定义决定了这类方法的压缩比.下面证明了k-RPC算法在所有支持k可达查询的基于等价类的图压缩算法中是最优的,即,任意一种支持k可达查询的基于等价类的图压缩算法得到的压缩图一定不会比G_R更小.

我们首先形式化地给出支持k可达查询的基于等价类的图压缩算法A的描述.给定原始图G=(V,E),算法A需要满足:

1) 算法A计算出的压缩图为G_A=(V_A,E_A),其中,V_A中的每个顶点[u]_A对应着原始图G中的一个顶点集合,边([u]_A,[v]_A)ÎE_A当且仅当在G中存在着两个顶点u_iÎ[u]_A和v_jÎ[v]_A,满足(u_i,v_j)ÎE;

2) 对于原始图G中给定的任意两个顶点u和v,u和v在G中是否k可达的查询结果与[u]_A和[v]_A在压缩图G_A中是否k可达的查询结果是相同的.

下面通过定理2和定理3分别证明:k-RPC算法在所有基于等价类的图压缩算法中是顶点数最小的和边数最小的.

定理2. 给定原始图G,G_R=(V_R,E_R)是k-RPC算法得到的压缩图,A是支持k可达查询的基于等价类的图压缩算法,且A计算出压缩图为G_A=(V_A,E_A),那么|V_A|≥|V_R|.

证明:假设存在一种基于等价类的算法A^*,A计算出的压缩图满足<|V_R|,那么在V_R中,一定存在着两个顶点[u]_R和[v]_R,使得等价类[u]_R和[v]_R中存在着两个顶点u_i和v_j满足;否则,中一定至少包含了|V_R|个顶点.

因为顶点u_i和v_j在V_R中对应着不同的等价类[u]_R和[v]_R,所以u_i和v_j的父亲和儿子不完全相同.假设y是u_i的儿子,且y不是v_j的儿子(反之亦可),下面考虑顶点y是否在中:

1) 如果yÎ,那么,否则,给定查询“顶点u_i和y是否邻接”,我们将回答“否”,这是错误的;但是给定查询“顶点v_j和y是否邻接”,因为,我们将给出肯定回答,而这也是错误的;

2) 如果顶点yÏ,假设yÎ,那么,否则,给定查询“顶点u_i和y是否邻接”,我们将回答“否”,这是错误的;那么类似地,给定查询“顶点v_j和y是否邻接”,因为,我们将回答“是”,这同样也是错误的.

上述错误说明:压缩图不能支持k可达查询,矛盾.如果u_i和v_j的儿子完全相同,类似地,也可以找到u_i和v_j不同的父亲,从而推出矛盾.

定理3. 给定原始图G,G_R=(V_R,E_R)是k-RPC算法得到的压缩图,A是支持k可达查询的基于等价类的图压缩算法,且A计算出压缩图为G_A=(V_A,E_A),那么|E_A|≥|E_R|.

证明:图G中,边通过压缩算法A也被划分为不同的等价类.例如,当图 1(a)中的顶点v₂和v₄被压缩为图 1(c)中的一个等价类{v₂,v₄}时,边(v₁,v₂)和(v₁,v₄)也会随之被压缩为一条边(v₁,{v₂,v₄}).由此可知,图G中的两条边(x₁,y₁)和(x₂,y₂)会被A压缩为一条边当且仅当[x₁]_A=[x₂]_A并且[y₁]_A=[y₂]_A.

假设存在一个基于等价类的图压缩算法A^*,使得A^*计算出的压缩图满足<|E_R|,那么G中一定存在两条边(x₁,y₁)和(x₂,y₂),满足并且,但是[x₁]_R¹[x₂]_R或者[y₁]_R¹[y₂]_R;否则,|E_A*|≥|E_R|.

不妨假设[x₁]_R¹[x₂]_R,因为,根据定理2,可以证明压缩图不支持k可达查询.因此,不存在一个基于等价类且支持k可达查询的图压缩算法A^*,使得A^*计算的满足<|E_R|. 

结论1. 给定原始图G,G_R=(V_R,E_R)是k-RPC算法得到的压缩图,A是支持k可达查询的基于等价类的图压缩算法,且A计算出压缩图为G_A=(V_A,E_A),那么|G_A|≥|G_R|.

证明:根据定理2和定理3,结论显然成立.

3k-RPC算法的改进

通过结论1,说明了在所有支持k可达查询的基于等价类的图压缩算法中,k-RPC算法计算出的压缩图具有最小规模.但是我们发现,k-RPC使用的等价关系比较严格,例如在图 1(b)中,顶点v₆和v₇具有一部分相同的父亲和儿子,但是[v₆]_R¹[v₇]_R.当原始图变得稠密时,该等价关系将不容易满足.假设原始图中任意的顶点u都以相同的概率与其他顶点邻接,那么在一个平均度为1的稀疏图上,任意的顶点u和v满足uºv的概率为O(1/n);当原始图的平均度上升为2时,uºv的概率将变为O(1/n²).

另一方面,注意到在稠密图中,顶点仍然具有公共的邻居.因此,如果从图 1(b)中删除边(v₅,v₆),(v₆,v₇)和(v₇,v₅),那么顶点v₆的父亲和儿子分别为{{v₂,v₄}}和{v₉},顶点v₇的父亲和儿子分别为{{v₂,v₄}}和{v₉},此时它们满足等价关系,可以归为一个等价类.于是可以得到一个新的压缩图,如图 1(c)所示.

基于上述发现,为了使k-RPC更好地适用于原始图较为稠密的情况,我们首先从原始图中删除一部分边使之变得稀疏,从而令更多的顶点可以满足等价关系.显然,删除的边集合E⁺将直接影响到k-RPC的压缩效果.于是,我们提出了最优边集问题来计算使压缩图最小的E⁺.下面将给出最优边集问题的形式化定义,并证明该问题是NP-hard的.

3.1 最优边集问题及其复杂度分析

记删除的边集合为E⁺,将删除了E⁺后的原始图G记为G^-=(V ^-,E ^-)=(V,E\E⁺).G^-可以通过k-RPC算法被压缩为可以发现,k-RPC算法计算出的压缩图G_R是E⁺=Æ时的特例.因为删除边会使原始图中顶点间的最短距离增加,所以需要保存E⁺,故压缩图共包括两个部分:压缩图本身和边集合E⁺.

定义2. 给定原始图G,E⁺ÍE是删除的边集合,G^-=(V,E\E⁺)可以通过k-RPC算法压缩为.最优边集问题就是计算出E⁺,使得||+|E⁺|最小.

记为最优压缩图,那么计算是NP-hard的.我们通过将3-SAT问题规约到该问题来证明这一点.规约分为两个部分:1) 首先,将3-SAT问题规约为满足m>n的3-SAT问题,其中,m表示短语数,n表示变量数; 2) 然后,将满足m>n的3-SAT问题规约为最优边集问题.对任意的3-SAT问题,我们将相应地构造一个原始图,并证明此3-SAT问题是可以满足的当且仅当该原始图压缩后不超过(9m+2)n+59m+2n.

定理4. 给定任意的3-SAT问题A,A包含n_A个变量和m_A个短语,那么一定存在一个3-SAT问题B,B包含n_B个变量和m_B个短语,且m_B>n_B,使得A可满足当且仅当B可满足.

证明:如果m_A>n_A,令B=A即可.否则,向A中加入3个变量x₁,x₂,x₃和4个短语(x₁Úx₂Úx₃)Ù(x₁ÚÚx₃)Ù(x₁Úx₂Ú )Ù(x₁Ú),得到一个新的3-SAT问题A¢.显然,A可满足当且仅当A¢可满足.

重复上述过程(n_A-m_A+1)次,可以得到B.

定理5. 给定任意的3-SAT问题满足m>n(其中,n表示变量数,m表示短语数),均可将其规约为最优边集问题.

证明:给定一个3-SAT问题,其变量为x₁,x₂,…,x_n,短语为C₁,C₂,…,C_m,我们相应地构造一个原始图G,如图 2所示,具体构造过程如下:

· 首先,对于每个变量x_i,1≤i≤n,向G中加入顶点x_i,和y_i,如图 2中第3行顶点所示;然后,再向G中加入2m个顶点x_i,1,x_i,2,…,x_i,2m,如图 2中第2行顶点所示,令x_i,1,x_i,2,…,x_i,m为顶点x_i的父亲,x_i,m+1,x_i,m+2,…,x_i,2m为顶点的父亲,x_i,1,x_i,2,…,x_i,2m为顶点y_i的父亲;最后,为每个x_i,k加入3个顶点作为父亲,记作u_i,k,v_i,k和w_i,k,其中,1≤k≤2m,如图 2中第1行顶点所示;

· 然后,对于每个短语C_j,1≤j≤m,向G中加入顶点C_j,1,C_j,2和C_j,3,如图 2中第4行顶点所示;然后,再向G中加入12个顶点a_j,1,a_j,2,…,a_j,12,如图 2中第5行顶点所示,令a_j,1,a_j,2,…,a_j,8为C_j,1的儿子,a_j,5, a_j,6,…,a_j,12为C_j,2的儿子,a_j,1,a_j,2,…,a_j,4,a_j,9,a_j,10,…,a_j,12为C_j,3的儿子;最后,为每个a_j,r加入3个顶点作为儿子,记作b_j,r,c_j,r和d_j,r,其中,1≤r≤12,如图 2中第6行顶点所示;

· 最后,对于每个短语C_j=(z₁Úz₂Úz₃),向G中加入3条边(z₁,C_j,1),(z₂,C_j,2)和(z₃,C_j,3).例如,如果C_j=(x₁ÚÚx₃),那么加入的边为(x₁,C_j,1),(,C_j,2)和(x₃,C_j,3),如图 2中第3行与第4行顶点之间的边所示.至此,完成了对原始图G的构造.

下面考察如何压缩G.可以发现,原始图G中的顶点分为6层且不同层次上的顶点没有相同的父亲或儿子,因此我们将逐层进行压缩.

首先,u_i,k,v_i,k和w_i,k应该被压缩为1个顶点.否则,x_i,k一定和其他顶点具有相同的父亲或儿子,因此被压缩并删除了与u_i,k,v_i,k和w_i,k之间的边.故,共有以下两种压缩方案:1) 将x_i,p和x_i¢,q合并为一个顶点;2) 将x_i,p和x_i¢,q的父亲顶点分别压缩,其中,1≤i¢≤n.当i=i¢时,对于任意的x_i,p和x_i,q,1≤p,q≤2m,它们没有相同的父亲并且至多有两个相同的儿子,此时,显然后者的压缩效果更好;当i¹i¢时,对于任意的x_i,p和x_i¢,q,1≤p,q≤2m,它们没有相同的邻居,此时也是后者的压缩效果更好.类似地,b_j,r,c_j,r和d_j,r应该被压缩为1个顶点,其中,1≤r≤12,并且a_j,r和a_j¢,s不会合并,其中,1≤j¢≤n,1≤s≤12.

还可以发现,顶点x_i和y_i、和y_i都有m个相同的父亲,且顶点x_i和的儿子都不超过m个,因此,应该将顶点x_i和y_i或者和y_i压缩为1个顶点.根据对称性,这两种压缩方案都可以采用.类似地,顶点C_j,1,C_j,2和C_j,3两两之间都有4个相同的儿子,且没有相同的父亲,因此应将其中两个压缩为1个顶点.同样根据对称性,这3种压缩方案都可以采用.

到目前为止,还有可能被压缩的顶点只剩下{x_i,|1≤i≤n}中的n个和{C_j,1,C_j,2,C_j,3|1≤j≤m}中的m个,且它们之间有m条边.记{x_i,|1≤i≤n}中未被压缩的顶点为{z_i|1≤i≤n},{C_j,1,C_j,2,C_j,3|1≤j≤m}中未被压缩的顶点为{C_j,f(j)|1≤j≤m},其中,f:{1,2,…,m}®{1,2,3}.可以发现:{z_i|1≤i≤n}中任意两个z_i和z_i¢都没有相同的邻居,所以不会被合并;而{C_j,f(j)|1≤j≤m}中任意两个C_j,f(j)和C_j¢,f(j¢)也没有相同的儿子,如果它们没有相同的父亲,那么它们也不会被合并.

如果给定的3-SAT问题是可满足的,那么令{z_i|1≤i≤n}为一组可满足赋值.假设x₁=1,x₂=0,…,x_n=1使3-SAT问题可满足,则令z₁=x₁,z₂=,…,z_n=x_n.然后,通过调整映射f,一定可以使每个C_j,f(j)在{z_i|1≤i≤n}中都有一个父亲,而具有相同父亲的C_j,f(j)可以被压缩为1个顶点,因此,{C_j,f(j)|1≤j≤m}会被压缩至不超过n个顶点;反之,如果{C_j,f(j)|1≤j≤m}可以被压缩至不超过n个顶点,那么{C_j,f(j)|1≤j≤m}的父亲顶点也一定不超过n个,而这些父亲顶点对应的赋值也一定使3-SAT问题可满足.至此,我们完成了给定3-SAT问题到最优边集问题的规约.

下面分析压缩图的大小.首先,对于每一个变量,因为u_i,k,v_i,k和w_i,k被压缩为1个顶点,所以共有2m个顶点;而x_i,k未被压缩,所以仍有2m个顶点;u_i,k,v_i,k,w_i,k与x_i,k之间的边则被压缩为2m条.假设x_i和y_i被合并,那么{(x_i,k,y_i)|m+1≤i≤2m}将被删除并加入E⁺;x_i,k与{x_i,y_i}之间的边被压缩为m条;x_i,k与之间的边仍为m条.故,这一部分压缩图的大小为(9m+2)n.

然后,对于每一个短语,类似地,它的儿子a_j,r未被压缩,所以仍有12个顶点;而b_j,r,c_j,r和d_j,r被压缩为1个顶点,所以共有12个顶点;a_j,r与b_j,r,c_j,r,d_j,r之间的边被压缩为12条.假设C_j,1和C_j,2被合并,那么{(C_j,1,a_j,r)|1≤r≤4}和{(C_j,2,a_j,r)|9≤r≤12}将被删除并加入E⁺;{(C_j,3,a_j,r)|1≤r≤4Ú9≤r≤12}也会被删除并加入E⁺;{C_j,1,C_j,2}与a_j,r之间的边被压缩为4条;C_j,1,C_j,2与它们父亲之间的两条边也会被删除.再考虑到顶点{C_j,1,C_j,2},那么,这一部分压缩图的大小为59m.如果3-SAT问题可满足,那么{C_j,3|1≤j≤m}可以被压缩至不超过n个顶点,C_j,3与之间的边也不超过n条.因此,压缩图的规模将不超过(9m+2)n+59m+2n. 

显然,定理4中的规约和定理5中原始图的构造都可以在多项式时间内完成,因此,最优边集问题是NP-hard的.

3.2 图压缩算法k-GRPC

我们给出了一种启发式图压缩算法k-GRPC,如算法2所示.k-GRPC算法迭代地从原始图G中选择“合适的”两个顶点进行合并,直至所有的顶点均不能再被合并.压缩图随着算法的运行不断发生变化,其最终结果为压缩图.

Algorithm 2. k-GRPC.

Input: Compressed Graph G_R=(V_R,E_R);

Output: Compressed Graph .

① V_tmp=V_R, E_tmp=E_R, count=0;

② while count<s do

//连续采样得到将要压缩的顶点对

③ random generate u;

④ pick w from u’s neighbors randomly;

⑤ choose v from w’s neighbors randomly;

⑥ compute C(u,v), Del(u,v), Exr(u,v);

⑦ If |C(u,v)|>Del(u,v)-|Exr(u,v)| do

⑧ compress u and v;

⑨ count=0, update V_tmp and E_tmp accordingly;

⑩ else

⑪ count++;

⑫ end if

⑬ end while

⑭ Return =(V_tmp,E_tmp);

判断图中两个顶点u和v是否“合适”,取决于将它们归为一个等价类后是否可以提高压缩比.如算法第7行所示(关于第7行中的判断条件,我们将稍后加以说明):如果图中的两个顶点在压缩后可以使压缩图的大小||+|E⁺|减少,则它们是“合适的”;如果图中任意两个顶点都不是“合适的”,则算法终止.判断两个顶点是否“合适”,应考察两个因素:一方面,每合并两个顶点都会使||减小1,故需要考察||+|E⁺|的变化;另一方面,还需要考察|E⁺|的变化,这是由于|E⁺|中的边没有被压缩,故,|E⁺|的增大会导致压缩比的下降.

综上所述,在选择“合适的”顶点对u和v进行合并时,算法首先使|E⁺|增加的最少;当出现相等的情况时,再使||+|E⁺|下降的最多.

由于k-RPC算法是将满足等价关系的顶点合并为一个等价类,而满足等价关系的顶点在合并后不会从原始图G中删除边,即,不会改变|E⁺|,因此,如果在原始图上调用k-GRPC算法,当|E⁺|第1次不为0时,计算出的压缩图恰为G_R.因此,在使用k-GRPC算法时可以直接以压缩图G_R作为输入.值得注意的是,k-GRPC算法可能进一步压缩G_R中的单个顶点或者压缩后的顶点.

例如,在对图 1(a)中的原始图G进行压缩时,将直接使用图 1(b)中的压缩图G_R作为输入.因为顶点v₆的父亲和儿子分别为{{v₂,v₄},v₅}和{v₇,v₉},顶点v₇的父亲和儿子分别为{{v₂,v₄},v₆}和{v₅,v₉},所以合并顶点v₆和v₇需要删除边(v₅,v₆),(v₆,v₇)和(v₇,v₅),此时,|E⁺|会增加3;而它们相同的父亲和儿子包括{v₂,v₄}和v₉,故,||+|E⁺|会减小2.因此,v₆和v₇是“合适的”,故算法将合并顶点v₆和v₇完成1次压缩.此后,图中任意两个顶点均不能合并,算法终止,最终得到了图 1(c)所示的压缩图.

下面来逐步说明算法第7行的判断条件.

首先,在算法执行过程中,需要为每一对顶点计算它们相同的父亲和儿子的C(u,v)以及不同的父亲和儿子的Ex(u,v),其中,

C(u,v)=(child(u)Çchild(v))È(father(u)Çfather(v)) (1)

Ex(u,v)=(child(u)Èchild(v)Èfather(u)Èfather(v))-C(u,v) (2)

在压缩两个顶点u和v之前,为了使它们具有相同的父亲和儿子,需要从图中删除顶点u和v与它们不同的父亲和儿子Ex(u,v)之间所有的边.因为顶点u和v之间的边(u,v)在child(u)和father(v)中重复计算了2次,所以,实际需要考虑的不同父亲和儿子Exr(u,v)满足:

Exr(u,v)=Ex(u,v)-E(u,v) (1)

其中,E(u,v)满足:

(4)

以对于图 1(b)中的压缩图G_R为例,根据公式(3)和公式(4),我们有|C(v₆,v₇)|=2,|Exr(v₆,v₇)|=3.u和v与Exr(u,v)之间边的数量并不一定恰好为|Exr(u,v)|,因为顶点u,v和Exr(u,v)中的顶点可能是等价类,所以,删除的边数Del(u,v)满足:

(5)

根据公式(5),我们有Del(v₆,v₇)=2+1=3.

如果顶点u和v是等价类,那么删除它们与Exr(u,v)之间的边就会使已经压缩的边被解压缩.因为合并顶点u和v需要删除Del(u,v)条边,而在合并前的图中,这部分边压缩为|Exr(u,v)|条,所以合并u和v后压缩图的规模将增加Del(u,v)-|Exr(u,v)|;如果合并的收益|C(u,v)|<Del(u,v)-|Exr(u,v)|,那么顶点u和v不会被合并,如算法第7行所示.

由于选择最优的顶点对需要一一考察O(|V_R|²)个顶点对,对于规模较大的图数据,上述时间开销将非常巨大.本文给出了线性时间的随机采样策略,如算法第2行~第5行所示.采样过程首先从V_R中随机选择一个顶点u,然后从u的邻居中随机选择顶点w,再从w的邻居中随机选择顶点v,最后判断顶点u和v是否是“合适的”.这样做是因为“合适的”顶点对至少应有一个公共邻居.如果连续s次随机采样到的顶点对都不是“合适的”,则终止采样算法.易知,该采样服从几何分布.假设每一次采样成功的概率为p,那么不超过s次得到“合适”顶点对的概率为1-(1-p)^s.为了使s次采样成功的概率不低于p₀,可以令s=⌈log_(1-p)(1-p₀)⌉.关于p值的计算我们仍然可以通过采样方法来估计,采样策略与算法2第3行~第5行的类似,假设在总共N次采样中得到了M对“合适的”顶点,那么p=M/N,本文的实验中设定p₀=0.999,N=10000.尽管每压缩一对“合适”顶点就会使剩余的“合适”顶点对减少,但是因为此时顶点数也会随之减小,故在s次连续采样过程中将不更新p值.

下面分析k-GRPC算法的近似比.由于k-GRPC算法是以G_R作为输入,故||+|E⁺|≤|G_R|.对于最优压缩图,可以证明||+|E|≥|V_R|,其中,E表示最优边集问题的最优解.于是,k-GRPC算法的近似比就是(1+|E_R|/|V_R|).

定理6. 给定原始图G,G_R=(V_R,E_R)是k-RPC算法得到的压缩图,E和是最优边集问题的最优解和最优压缩图,那么||+|E|≥|V_R|.

证明:易知,可以在G_R上通过删除边和划分等价类得到.这就意味着,对于任意的顶点u和v,如果[u]_R=[v]_R,那么它们在中也一定被划分为一个等价类.否则,记u和v所属等价类为[u]_Opt和[v]_Opt,用nei([u]_Opt)表示[u]_Opt在压缩图中的邻居,用neiE^*(u)表示u在E^*中的邻居.不妨假设|nei([u]_Opt)|+|neiE(u)|≤|nei([v]_Opt)|+|neiE(v)|.因为father(u)=father(v)且child(u)=child(v),因此可将v移动至等价类[u]_Opt.显然,压缩图的规模不会扩大.

因此,压缩图是将G_R中的等价类进一步合并了.因为任意两个等价类的合并都至少向E^*中增加1条边,所以|V_Opt|+|E|≥|V_R|.那么显然,||+|E|≥|V_R|. 

事实上,尽管压缩图中的顶点代表一个等价类,而边集合E⁺中的顶点表示单个顶点,我们仍然可以将二者存储在一起.为保证查询的正确与效率,存储应当满足以下规则:1) 对压缩图与E⁺中的边,仍然使用邻接表的形式存储,且保证有序;2) E⁺中的顶点使用原始图中的id,中的顶点使用不同的id以示区分;3) 压缩图与E⁺中的边交替存储,首先是中第1个顶点[u₁]_R在中的邻接表,然后是[u₁]_R中每一个顶点在E⁺中的邻接表,再然后是中第2个顶点[u₂]_R的邻接表,然后又是[u₁]_R中每一个顶点在E⁺中的邻接表,….例如,对于图 1(b)所示的压缩图G_R,通过向E⁺中增加(v₅,v₆),(v₆,v₇)和(v₇,v₅),可以得到图 1(c)所示的压缩图,那么根据规则2,{v₁}的id为10,{v₂,v₄}的id为11,以此类推;然后根据规则3,边将按照以下顺序存储:

(v₁₀,v₁₁),(v₁₀,v₁₂),…,(v₁₃,v₁₅),(v₅,v₆),(v₁₄,v₁₆),(v₆,v₇),(v₇,v₅),

其中,v₁₃,v₁₄,v₁₅和v₁₆分别表示{v₅},{v₆,v₇},{v₈}和{v₉}.将压缩图和边集合E⁺连续存放的好处是:可以连续访问一个等价类中全部顶点的邻居,从而减少I/O代价.

下面分析算法2的时间复杂度.在每次迭代过程中,k-GRPC将两个顶点压缩为1个,故算法迭代的次数为O(s|V_R|).在每次迭代中,算法第3行~第5行的随机采样过程将从随机生成顶点u的一个随机邻居中再次随机选择一个邻居,故,时间复杂度为O(avg(deg(u)));算法第6行中,计算C(u,v),Exr(u,v)和Del(u,v)需要顺序访问顶点u和v的邻居,其时间复杂度为O(deg(u)+deg(v))=O(avg(deg(u)))=O(|E_R|/|V_R|);算法第8行~第9行中,合并两个顶点并更新压缩图可以在常数时间内完成.综上所述,算法2的时间复杂度为O(s|E_R|).另外,算法2使用了k-RPC算法计算的压缩图作为输入,故k-GRPC算法总的时间复杂度为O(s|E_R|+|E|log|V|).

当原始图发生了动态更新时,可以通过如下操作实现更新:1) 对于孤立顶点的插入/删除,可以直接向孤立顶点等价类中插入或者从其所在等价类中删除即可;2) 对于边的插入,可以直接将新增的边加入E⁺;3) 对于边的删除,可以从压缩图中删除边([u]_R,[v]_R),其中,[u]_R和[v]_R表示顶点u和v所属的等价类.另外,还应把[u]_R中所有顶点与[v]_R中所有顶点之间的边加入E⁺.易知,边的插入/删除会导致E⁺不断增大并影响查询效率,而由于压缩图G_R可以随时准确更新,我们可以定期地在G_R上调用k-GRPC算法重新计算压缩图和E⁺.由于动态图并不是本文的研究对象,故对压缩图G_R和上的动态更新技术本文不再作详细探讨.

3.3 基于k-GRPC压缩图的查询处理算法

k-GRPC算法虽然可以提高压缩比,却不能直接在压缩图上完成查询处理.这是因为,当使用压缩图G_R计算d(G,u,v)时,根据定理1,可以直接计算出d(G_R,[u]_R,[v]_R)即可;而由于原始图G中一部分边被删除并保存在E⁺中,使用压缩图计算的d(,[u]_R,[v]_R)是d(G,u,v)的上界.

我们仍然可以使用类似广度优先的算法完成查询,见算法3.算法需要建立一个优先队列QA,队列中的顶点可以是单个顶点或者等价类,并仍然按照与顶点u之间的距离从小到大排序.对于队首顶点x,其邻居一定包含两部分:压缩图中的等价类和E⁺中的顶点,分别如算法第6行~第8行和第9行~第11行所示.下面分别讨论x是单个顶点和等价类的情况:

1) 当x是单个顶点时,中的邻居可以从[x]_R的邻接表访问,E⁺中的邻居可以直接从x在E⁺中的邻接表访问;

2) 当x是等价类时,中的邻居可以直接从x的邻接表访问,E⁺中的邻居可以从x的所有顶点在E⁺中的邻接表访问.

由于上述两种情况比较相似,在算法3中不再加以区分.

Algorithm 3. QueryG^-.

Input: Compressed Graph , Removed Edge Set E⁺, Vertex u and v, Value k;

Output: ‘Yes’ if u can reach v within k-hops or ‘No’ otherwise.

① d[u,u]=0, push(u,Q);

② for each vÎ do

③ d[u,v]=¥;

④ while Q is not empty do

⑤ w=pop(Q);

⑥ For each vertex xÎÙ(w,x)ÎÙd[u,x]>d[u,w]+1

//访问压缩图中的边

⑦ d[u,x]=d[u,w]+1, pushQ(x,Q);

⑧ end for

⑨ For each vertex xÎ[w]_RÙ(x,y)ÎE⁺Ùd[u,y]>d[u,x]+1

//访问E⁺中的边

⑩ d[u,y]=d[u,x]+1, pushQ(y,Q), split y from [y]_R;

⑪ end for

⑫ end while

⑬ If d[u,[v]_R]≤k

⑭ Return ‘Yes’;

⑮ Return ‘No’;

需要指出的是:当单个顶点x出现在队首时,一定满足d(u,x)<d(u,[x]_R).这里,[x]_R是顶点x在中所属的等价类.为了区分顶点x和[x]_R中的其他顶点,算法将x从等价类[x]_R中分裂并形成一个新的等价类.新等价类仅包含x一个顶点.

下面分析查询算法3的复杂度:一方面,优先队列QA中出现的顶点包括中的等价类和这些等价类分裂出的顶点,而由于每访问E⁺中的一条边至多将导致一个顶点的分裂,故,QA中的顶点不超过O(||+|E⁺|)个;另一方面,算法访问的边集为和E⁺.因此,在压缩图上查询处理的时间复杂度为

因为在压缩图G_R上查询的时间复杂度为O(|V_R|+|E_R|),所以使用压缩图查询的时间复杂度更低.但是,因为在查询压缩图G_R时只需要访问每个顶点和边各1次,而算法3不仅需要访问E⁺中的边1次,并且由于E⁺中边的访问,又可能导致等价类分裂O(|E⁺|)次,即,需要额外访问O(|E⁺|)个顶点.基于上述原因,通过真实数据上的实验验证:

· 在稀疏图上,两种压缩算法的压缩比相当.此时,基于k-RPC压缩算法的查询处理效率略好于基于k-GRPC压缩算法的查询处理效率;

· 在稠密图上,由于k-GRPC具有较好的压缩比,所以其查询效率明显高于基于k-RPC算法的查询效率.

4 实验结果

在实验部分,我们在真实数据上对两种压缩算法的有效性、压缩效率和查询效率进行了考察.对比实验包括基于顶点覆盖的索引VC^[1],2-hop VC^[1]和BFS算法.下面首先介绍实验考察的几种测度,包括压缩算法压缩比、运行时间和查询处理时间;随后介绍使用的实验数据、实验环境和对比实验;最后给出实验的对比及分析.

在考察算法的压缩比时,分别用CR_k和CR_kG表示压缩方法k-RPC和k-GRPC算法的压缩比,其中,

CR_k=(|V_R|+|E_R|)/(|V|+|E|),CR_kG=(+|E⁺|)/(|V|+|E|).

可知:压缩比越小,压缩图的规模也越小,说明压缩算法更加有效;在考察压缩算法的运行时间时,由于k-GRPC算法是以k-RPC算法计算的压缩图作为输入,因此我们认为,k-GRPC算法的压缩时间应包含k-RPC的压缩时间;在考察查询处理时间时,对比了两种基于压缩图的查询处理算法的时间开销与在原始图上直接进行查询处理的时间开销.

本文的全部实验在真实的数据集上进行.实验数据包括:1) 斯坦福大学的共享数据集(http://snap.stanford. edu/data/#twitter);2) 国内科研数据共享网站数据堂中数据挖掘数据库(http://www.datatang.com/).本文使用的数据规模在685K~8.3M之间,包括了以下网络:1) Email-EuAll¹、欧盟科研机构之间的邮件网络和wiki-Talk¹、维基百科网站上的交互网络;2) Web-NotreDame¹,Web-Google¹,Web-Stanford¹和Web-BerkStan¹等网络图;3) Twitter²,一个在线社交网站.表 1中给出了本文使用的社交网络的特性,其中,p表示在压缩图G_R上随机采样到“合适”顶点对的概率,s表示为了使s次采样成功的概率不低于99.9%的采样次数.

上述实验使用C++实现,在双核3.40GHz Intel Core(PM) D CPU,32.0GB内存,Windows Vista系统的台式机上运行.

基于顶点覆盖的索引VC和2-hop VC是目前能够有效处理k可达查询的方法,其索引的规模甚至不超过某些支持可达查询索引的规模^[1].但是这两种索引仍然不能扩展到规模较大的图上,且只能回答特定k值下的k可达查询,而如果需要精确查询,则必须构建一系列索引.由于2-hop VC要求k>2h=4,故,在实验中构造了支持k值为5的可达查询索引.

表 2给出了两种压缩方法和VC,2-hop VC在全部数据集上的压缩比对比情况.按照图数据的平均度数,我们对7个真实数据集上的压缩结果进行了比较.可以发现:在最稀疏的Email-EuAll上,k-RPC算法的压缩比最好,可以达到35.2%,但是随着图的平均度数的增大,k-RPC算法的压缩比也随之上升,其中在Web-Google上,压缩比最差,达到了的81.1%.注意到,k-RPC在平均度数更大的Web-Stanford和Web-BerkStan上的压缩比反而更好,处于70%~75%左右.这是由于在校园社会网络中更多出现相同邻居的特点,即,一个学术团队内的人往往有着共同的联络对象.但从整体上来看,随着图平均度数的增大,k-RPC的压缩效果会随之下降.

我们还可以发现,k-GRPC的压缩比一直好于k-RPC的压缩比.这是由于k-GRPC算法是在k-RPC的基础上进一步压缩的.当原始图比较稀疏时,例如在wiki-Talk上,两种算法的压缩比非常接近,分别为49.4%和49.1%;而随着图的平均度数的增加,k-GRPC的压缩比将明显好于k-RPC的压缩比.例如在Web-Stanford上,两种算法的压缩比分别为75.1%和62.1%.这是由于k-RPC严格的等价关系在较为稠密的图上不易满足所致.

VC和2-hop VC构建的索引要远远大于原始图的规模,且随着图平均度数的增大显著递增.在Web-Google和Web-BerkStan上,两种索引图甚至分别超过了700M和2G条边,并超过了原始图规模的119倍和241倍.如果进一步考虑到索引需要保存的权值信息,上述索引将更加庞大.而如此庞大的索引却仅能准确回答k值为5的k可达查询,而随着k值的增大,基于索引的方法还需要构建更大规模的索引来支持查询处理.

表 3给出了两种压缩算法的压缩时间与VC,2-hop VC方法构建索引时间的对比.可以发现:k-RPC和k-GRPC算法的压缩时间是随着数据集规模的扩大呈线性增加的,这与之前的分析是一致的;而构建VC,2-hop VC索引的时间则是随着数据集规模的扩大而显著增加的,这是由于两种方法构建索引规模的显著扩大所致.其中,在规模为2.59M的Web-Stanford上,VC和2-hop VC甚至不能在1小时内完成索引的构造.

表 4给出了基于压缩算法的查询时间与基于索引方法的查询时间对比情况,实验随机生成了10 000组查询,并给出了平均查询时间.可以发现:当原始图比较稀疏时,基于k-RPC算法的查询效率明显好于BFS算法,例如在Email-EuAll,twitter上,前者的查询效率是后者的2.5倍以上;而随着图的平均度数变大,基于k-RPC的查询效率将逐渐接近原始图上的查询效率,达到1.3倍左右.这是由于,基于压缩图的查询效率是与压缩图的规模相关的,随着图数据变得稠密,k-RPC的压缩效果会下降,故查询效率也会随之下降.

我们还可以发现,基于k-GRPC的查询效率在稀疏图上略低于基于k-RPC的查询效率.这是由于两种压缩算法在稀疏图上的压缩比非常接近,而基于k-GRPC的查询由于需要访问+2|E⁺|个顶点和边,故,查询效率会有所下降.当图变得比较稠密时,基于k-GRPC的查询效率会明显好于基于k-RPC的查询处理.例如,在Web-Stanford上,两种基于压缩图的查询处理算法效率分别是BFS算法的1.35倍和1.50倍.这是由于,在比较稠密的图上,k-GRPC仍然可以对k-RPC计算的压缩图进行有效的压缩,从而提高查询效率.

基于两种索引方法的查询效率是与索引规模直接相关的,故,在规模较小的Email-EuAll上,其查询效率较好,达到了BFS算法的750倍左右;但是随着数据规模的扩大,在规模约为Email-EuAll 1.9倍的twitter上,两种查询算法的效率迅速下降至仅为BFS算法的150倍;而当数据集进一步扩大时,基于索引的方法将由于索引过于庞大而无法使用.尽管在数据集规模较小时,基于索引的查询更加有效,但是由于它们不具备较好的可扩展性,因此无法适用在规模更大的数据集上.

综上所述,基于索引的方法只能适用于数据集规模较小的情况.对于规模较大的数据集,当原始图比较稀疏时,两种压缩算法的压缩比较为接近,此时,k-RPC算法更为适用;当原始图比较稠密时,k-GRPC算法的压缩比会明显好于k-RPC的压缩比,并具有更好的查询效率,故,此时k-GRPC更加适用.

5 结束语

本文研究了基于图压缩技术的k可达查询处理算法,提出了图压缩算法k-RPC及在压缩图上无需解压缩的查询处理算法,证明了基于图压缩算法k-RPC的查询处理的正确性,并证明了k-RPC在所有支持k可达查询的基于等价类的图压缩算法中是最优的.考虑到k-RPC的等价关系比较严格,在稠密图上不易满足,本文允许从原始图中删除部分边,并提出了最优边集问题,且证明了该问题是NP-hard的;还给出了线性的近似图压缩算法k-GRPC及在压缩图上无需解压缩的查询处理算法.通过真实数据上的实验结果表明:两种压缩算法的压缩比在稀疏图上可以达到45%,在稠密图上分别可以达到75%和67%,而查询效率在稀疏图上可以提高2.5倍.在今后的工作中,我们将进一步探讨针对本文压缩方法的有效查询处理算法和外存上有向图的图压缩算法.

致谢 在此,我们向对本文提出宝贵审稿建议的审稿专家以及哈尔滨工业大学计算机科学与技术学院的李建中教授表示衷心的感谢.