Scalable Query Relaxation for Semantic Association Search MG1733030 李舒馨 2017.11.06

摘要 当搜索一组实体的语义关系时，可能会出现某几个实体间不存在关联的情况，从而返回空的结果。 针对这种情况，提出查询松弛的设想，即在原始查询中去掉最少的实体，使得新的查询能够得到至少一组关联。 设计了一种算法在多项式时间内找到一个点（certificate）能够验证一组实体是否存在关联。 BSC 为了优化性能，基于距离计算每个候选certificate的优先级。 OPT 在OPT基础上，提出两种启发式。 基于点的度数。 OPTpd 到达certificate还需走的步数。OPTps 以上两种启发式结合。 OPTpds

{Alice,Dan} {Bob,Dan} Alice Bob Carol Dan Paper01 Paper02 Paper03 WWW2018 isAcceptedAt author memberOfPC Erin Frank supervisor 关联的存在性：基于直径 若查询实体为{Alice,Bob,Dan}，且限制直径=3，则搜索关联的结果为空（distance(Alice,Bob)=4） {Alice,Dan} {Bob,Dan} 查询松弛得到最大的一组关联子集：

certificate 给定图G，直径D，查询Q，Q存在关联当且仅当存在G中的一个点c满足： 对Q中的所有实体对于的点v，dist(v,c)<=ceil(D/2) 若D是奇数，则c存在一个邻居c'使得所有dist(v,c)=ceil(D/2)的点v也同时满足dist(v,c')=ceil(D/2)-1

certificate 必要性： vi vj c pi pj pij vk pk 关系x对应的图是一棵树 令Pij是最长的一条路径，且长度diam(x)<=D c为Pij的中间点，Pi=ceil(diam(x)/2)，那么Pj=ceil(diam(x)/2)或ceil(diam(x)/2)-1 以下证明c满足1和2两个条件

certificate 必要性： vi vj c pi pj pij vk pk 1.令Pk为vk和c之间的路径 若vk在Pij上，则Pk<=ceil(diam(x)/2) 若vk不在Pij上，Pk不能同时和Pi、Pj重叠，假设Pk不与Pj重叠，则Pk<=ceil(diam(x)/2)，否则Pk可以和Pj组成直径>diam(x)的图，矛盾。

certificate 必要性： pl … c' c vl 2.若D为奇数，令VQ2为所有满足dist(v,c)=ceil(D/2)的点v的集合 对于任意VQ2中的点vl，令Pl为vl与c之间的路径 由于dist(vl,c)=ceil(D/2)，则len(Pl)>=ceil(D/2)；根据条件1，len(Pl)<=ceil(D/2)。 所以Pl长度为ceil(D/2) 所有这些路径必须重叠，否则2*ceil(D/2)>D 即这些路径共用关联至c的一条边，令c'为该边的另一个顶点，则vl与c'之间的路径长度为ceil(D/2)-1，所以dist(vl,c')=ceil(D/2)-1

certificate 充分性： … c c' … c 根据条件1和2构造关联图x。 但x可能不是最小的，可能存在重边和环。

BSC 从所有查询节点出发，依次遍历邻居，ceil(D/2)为搜索的路径长度，找到一个v作为 certificate的最大查询。 OptWithCert找到v作为certificate的一个最大的子查询

OPT BSC搜索了所有路径长度<=ceil(D/2)的点 优化：一些点应该被优先搜索。点v可能可以到达的查询节点越多，则应该排在前面。 eq1 eq2 eq3 v len=1 dist=3 dist=4 D=4 v从eq1出发，且D=4 则priority(v)=2

OPT Alice Bob Carol Dan Paper01 Paper02 Paper03 WWW2018 isAcceptedAt author memberOfPC Erin Frank supervisor 给定D=3，Q={Alice,Bob,Dan} 最开始<Alice,Alice,2>，<Bob,Bob,2>，<Dan,Dan,3>会被加入优先队列PQ <Dan,Dan,3>最先被取出，接着搜索到它的邻居，将<WWW2018,Dan,3>加入PQ <WWW2018,Dan,3>被取出，且验证Qmax={Alice,Dan} 或 {Bob,Dan}

OPT OPT能够返回一个最大的成功子查询。 假设Qmax为算法得到的结果，Qopt为最优解，且|Qmax|<|Qopt| Qopt可以被c验证，即Qmax未被c验证过，否则会返回Qopt 以下证明c可以在终止前被验证： 可找到一条从查询节点sv出发到c的最短路径Pk，Pk上的所有点v'都满足priority(v'|sv)>|Qmax|，且<sv,sv,priority(sv)>在一开始就加入优先队列，所以sv一定会优先取出，接着会搜索到sv在Pk上的邻居，于是Pk上的点都会被搜索到，c一定会在终止前被验证。

OPT

启发式 推迟处理度数大的节点，搜索大度点的邻居且计算它们的priority很耗时 考虑节点和一个可能的certificate的距离，距离小的应该优先处理 结合以上两种

谢谢