面向大图的可达性查询处理算法

• 作者: 周军锋 李娜 陈伟 陈子阳
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 大图 有向无环图 可达性查询处理 最优生成树
• 年，卷（期）: 2019,（3）
• 所属期刊栏目: 人工智能
• 页码范围: 582-595
• 页数: 14页
• 分类号: TP301
• 字数: 11942字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2019.00582

摘要

图的可达性查询处理是生物信息领域的热点问题之一,用于测定蛋白质交互网络中任意两个蛋白质分子间是否存在交互作用.针对已有在可达查询比例增大时在线搜索算法效率下降明显及性能不稳定的问题,提出优化的OPT-R算法.首先,提出最优生成树的概念,使得采用最优生成树的OPT-R算法可以在常量时间回答更多的可达查询;同时提出基于栈的互逆拓扑顺序,使得OPT-R可以在常量时间回答更多的不可达查询.作者还提出相应的最优生成树及互逆拓扑顺序生成算法,并通过实验对基于20个不同规模的真实数据集从不同角度对算法的高效性进行了验证.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈伟	燕山大学信息科学与工程学院	14	64	5.0	7.0
3	李娜	燕山大学信息科学与工程学院	43	328	9.0	17.0
4	陈子阳	上海立信会计金融学院信息管理学院	27	100	6.0	9.0
6	周军锋	燕山大学信息科学与工程学院	21	167	6.0	12.0