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

摘要：

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

关键词：大图、有向无环图、可达性查询处理、最优生成树

所属期刊栏目：42

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金61472339,61572421,61272124

在线出版日期：2019-06-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：582-595