(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210667968.4 (22)申请日 2022.06.14 (71)申请人 大连理工大 学 地址 116024 辽宁省大连市甘井 子区凌工 路２ 号 (72)发明人 王鹏飞　李诗琪　张强　 (74)专利代理 机构 辽宁鸿文知识产权代理有限 公司 21102 专利代理师 王海波 (51)Int.Cl. G06F 16/36(2019.01) G06F 16/335(2019.01) (54)发明名称 一种基于频繁模式挖掘的边缘缓存知识图 谱划分方法 (57)摘要 本发明提供了一种基于频繁模式挖掘的边 缘缓存知识图谱划分方法， 属于数据处理技术领 域。 本发明利用查询图中挖掘出的频繁查询模 式， 对初始知识图谱进行着色， 通过改进交换算 法将知识图谱划分成不同颜色区域， 使划分后的 知识图谱在满足最小切割边的同时符合边缘缓 存大小。 在用户下一次访问时， 可 以快速响应出 周围所需服务场景的信息， 实现接近最优的缓存 性能。 本发 明将知识图谱合理部署 到边缘服务器 中， 使得周围用户可 以快速获取所需信息， 大大 减少了从云端获取数据的回程压力， 为用户提供 更好的交 互体验。 权利要求书2页 说明书6页 附图3页 CN 115129887 A 2022.09.30 CN 115129887 A 1.一种基于频繁模式挖掘的边缘缓存知识图谱划分方法， 其特征在于， 该方法包括以 下步骤： 步骤一： 边缘服务器根据历史查询生成查询图GQ＝{VQ， EQ， LEQ， LVQ}， 其中VQ代表点集； EQ 代表边集； LEQ是边标签， 表示频繁程度； LVQ是点标签， 表示类别属性； 步骤二： 基于查询图GQ进行频繁查询模式挖掘， 挖掘出频繁查询模式， 查询模式定义为P ＝{VP， EP， LEP， LVP}， 其中VP代表查询模式点集； EP代表查询模式边集； LEP是查询模式边标 签， 其中边标签都为空； LVP是查询模式点标签， 表示类别属性， 并且查询模式中没有重复的 点标签， 更加关注不同类别实体间的联系； 步骤三： 基于频繁查询模式对知识图谱进行初始着色， 将属于频繁查询模式上的点固 定为所属 边缘服务器包括的颜色， 根据边缘缓存容量的阈值 随机初始化其他节点的颜色， 然后应用启发式局部 搜索进行多路划分， 并将知识图谱推向低能状态； 步骤四： 根据不同颜色的分区将知识图谱划分到所属的边缘服务器上， 若当前服务器 中的由频繁查询模式扩展 出的知识图谱是非连通图， 则将根据频繁查询模式中节点的连接 在知识图谱中的两个节点之间建立 一条有向边， 并用当前服 务器名称命名有向边。 2.根据权利要求1所述的一种基于频繁模式挖掘的边缘缓存知识图谱划分方法， 其特 征在于， 所述 步骤二中， 频繁查询模式挖掘的具体步骤如下： 步骤2.1： 初始化结果 集和候选集 为空， 将查询图GQ中所有频繁边置 于频繁边 集中； 步骤2.2： 计算所有频繁边的路径图， 并将所有频繁边 生成的路径图并入候选集中； 步骤2.3： 频繁边e产 生的查询模式为p， 将查询模式p放入 空栈S中， 循环出栈； 如果栈顶 查询模式无法扩展或已经完全被扩展， 则将扩展后的查询模式并入结果集， 栈顶查询模式 出栈； 若栈顶查询 模式可以继续扩展， 则将查询 模式p扩展后记为p ′， 对p′进行路径图扩展 记为pgG(p′)； 步骤2.4： 初始路径图pgG(p′)置空， 并将查询模式p ′中的所有边加入到查询模式边集 中， 循环将查询模式边集中的频繁边e的路径图合并到查询模式路径图pgG(p′)中， 完成路 径图扩展； 步骤2.5： 若路径图pgG(p′)的最小独立个体支持大于规定阈值， 将扩展后的查询模式p ′ 放入栈中， 继续进行扩展； 栈为空时， 结束循环并将频繁边e从频繁边 集中移除； 步骤2.6： 重复步骤2.3和2.4， 直到频繁边集为空， 最终输出结果集中满足频繁阈值的 频繁查询模式。 3.根据权利要求1或2所述的一种基于频繁模式挖掘的边缘缓存知识图谱划分方法， 其 特征在于， 所述 步骤三中， 多路知识图谱划分的具体步骤如下： 步骤3.1： 从节点u的邻 居集中找出最优交换节点partner， 若邻 居集中无法找出最优 交 换节点， 则在样本集中寻找最优交换节点； 步骤3.2： 寻找最优交换节点方式如下： 对于邻居集或者样本集中的节点u进行循环计算， 节点u与节点v交换后的能量是否大 于交换前， 即 du( πv)α+dv( πu)α＞du( πu)α+dv( πv)α 其中， πv表示节点v的颜色， du( πv)表示节点u的邻居中与节点v颜色相同的节点数量； α 是能量函数的参数， 通过调节α 的值， 使图谱在实际划分中得到最佳 结果；权　利　要　求　书 1/2 页 2 CN 115129887 A 2步骤3.3： 为了避免陷入局部最优， 使用模拟退火技术； 引 入温度T参数， 其中温度参数 随时间增 加而降低； 若新能量new＝du( πv)α+dv( πu)α与温度Tr的乘积大于原能量old＝du( πu)α+dv( πv)α， 并且 为最大值， 则当前节点v即为 最优交换节点； 步骤3.4： 重复步骤3.2和3.3， 直到完全遍历邻居集或者样本集中的节点， 并逐步降低 温度Tr， 直到Tr为下限1时， 温度不再降低； 步骤3.5： 若最优交换节点非空， 则交换节点v与节点u的颜色。权　利　要　求　书 2/2 页 3 CN 115129887 A 3