一种高效的不确定图上k步可达查询处理算法

• 作者: 仲悦 杜明 周军锋
• 来源期刊: 新一代信息技术
• 关键词: 不确定图 k步可达 顶点覆盖
• 年，卷（期）: 2021,（5）
• 所属期刊栏目: 科技论文
• 页码范围: 1-8
• 页数: 8页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.2096-6091.2021.05.001

摘要

目的 给定一个不确定图,k步可达查询返回u到v在k步以内可达的概率.方法 目前关于k步可达的索引方法都只适用于确定图,而不确定图上通常采用直接抽样求估计值.结果 本文提出一种两阶段概率图上k步可达查询策略:首先基于顶点覆盖集构建确定图的k步索引,用于快速过滤肯定不可达的查询;其次针对不确定图,使用基于路径和提前抽样的方法来回答查询.结论 实验结果验证了本文方法的高效性.