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

发布时间：2023-05-31 23:28

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

【文章页数】：14 页

【文章目录】：
1 引言
2 背景知识和相关工作
    2.1 背景知识
    2.2 相关工作分析
        2.2.1 标签法
        2.2.2 在线搜索法
3 基本思想
    3.1 最优生成树及其性质
    3.2 基于栈的互逆拓扑顺序
4 算法描述
    4.1 索引构建
        4.1.1 求解互逆ST-order
        4.1.2 构建最优生成树区间
        4.1.3 算法分析
    4.2 查询处理
5 实验
    5.1 实验环境
    5.2 数据集
    5.3 性能比较及分析
        5.3.1 查询时间
        5.3.2 索引构建时间及索引大小
6 结论
Background



本文编号：3826217