基于属性图模型的近邻查询方法

摘要

本发明公开一种基于属性图模型的近邻查询方法，该方法将顶点集查询问题定义成属性图模型，从全局角度求解属性图中的top‑k具有最小直径的顶点集，通过渐进式搜索和最少优先算法等策略获取可行解空间。本发明方法能够形成解决全局情况下属性图中的top‑k最小直径顶点集方案，使属性图中的最小顶点集求解问题在解决过程在时间和空间复杂度上得到优化，并避免早熟收敛。

主权项

基于属性图模型的近邻查询方法，其特征在于，该方法包括以下步骤：步骤1)根据用户输入的信息，构建网络中的top‑k近邻查询问题的属性图模型G＝(V,E,A)，其中V是顶点集，E是边集，A是将一个顶点映射到一组属性的函数；所述属性图模型G在建立后，任意两个顶点之间的最短路都有最少需通过的边数，表示两者的邻近度，具体步骤如下：步骤11)用户输入包含一组属性的查询属性集、顶点集及每个顶点对应的属性集，给定直径约束及最优解的个数要求，其中，用户输入的查询属性集记为Q＝{a₁,a₂,…,a_m}，顶点集记为V，每个顶点到对应属性集的映射函数记为A，直径约束记为D，最优解的个数记k，所述m是查询属性集中属性的个数；所述A:其中Α是属性图G中不同属性的总集合，Α＝{a₁,a₂,…,a_n}，n表示总集合Α中属性的个数，表示幂集；步骤12)将顶点集中所有顶点看作属性图模型G＝(V,E,A)中的顶点；步骤13)将顶点u和顶点v之间的路径看作属性图模型G＝(V,E,A)两顶点之间的弧，两顶点之间的距离作为顶点u和顶点v之间弧的权值，所述d(u,v)为属性图模型G＝(V,E,A)中顶点u和顶点v最短路的权值，且顶点间的距离满足三角不等式；所述u,v∈V；所述三角不等式是指在三角形中，必然有两边之和大于第三边；步骤14)用P_u表示顶点u所代表的顶点具有的属性集；当a_j∈P_u，顶点u具有属性a_j，反之当时，顶点u不具有属性a_j，所述a_j是指第j个属性，其中1≤j≤n；步骤15)定义X(a_j)，表示由所有具有属性a的顶点构成的集合，其中|X(a_j)|表示X(a_j)中的顶点个数；步骤16)定义V的子集S，其中若则S覆盖查询属性集Q，S为一个查询覆盖顶点集；若不存在S的子集满足覆盖Q条件的情形，则S被称作最小覆盖；步骤17)定义顶点集S的直径为该顶点集中所有顶点对之间最短距离的最大值，记为diameter(S)＝max_u,v∈S{dist(u,v)}，所述dist(u,v)表示属性图模型G＝(V,E,A)中顶点u和顶点v之间的最短路径长度，所述diameter(S)表示顶点集S的直径；步骤2)采用渐进式搜索与最少优先算法，获得社交网络组队问题在属性图模型G＝(V,E,A)上的解空间，具体步骤如下：步骤21)定义查询属性集Q的最少属性a_l，所述a_l是属性图模型G＝(V,E,A)中最少顶点数包含的属性，其中a_l∈Q；步骤22)定义顶点u的d邻域为N_d(u)，所述N_d(u)是属性图模型G＝(V,E,A)中到u的最短距离不超过d的顶点集合；步骤23)定义索引距离d，并且初始化d＝1，所述索引距离d是引入的一个变量，用来辅助求解最小直径顶点集；步骤24)当解空间中的目标解个数没有达到目标要求k时，逐步放宽索引距离d的大小，再进行顶点集的搜索，直至索引距离不在直径约束范围内；步骤25)对于最少属性a_l，计算得到X(a_l)，对于X(a_l)中的每个顶点v′，求出相应的备选顶点集S′，所述S′是由N_d(v′)中的包含查询属性集Q中除最少属性a_l之外其他属性的v′与其最近邻居构成的顶点集；步骤26)计算备选顶点集S′的最小覆盖S″＝{S″₁,S″₂,…,S″_f,…,S″_g}，所述S″_f表示备选顶点集S′的第f个最小覆盖，其中0≤f≤g；步骤27)对于S′的每个最小覆盖S″_f，若还没有加入到已有解空间中，并且该最小覆盖对应的直径diameter(S″_f)不超过直径约束D，则将该最小覆盖保存到解空间S_olution中；步骤28)若解空间中的最小直径顶点集个数没有达到目标要求k，重复步骤24)～步骤27)；步骤29)确定最终解空间S_olution，该解空间中包含top‑k最小直径顶点集。