%0 Journal Article
%T 高效的多关键词匹配最优路径查询算法KSRG
%A 张兴忠
%A 牛保宁
%J 计算机应用
%D 2017
%R 10.11772/j.issn.1001-9081.2017.02.0352
%X 摘要 为改进基于关键词的最优路径查询算法，在大规模图以及多查询关键词下复杂度过高与可扩展性不足的缺陷，依据查询关键词序列构建候选路径的策略提出一种高效查询算法。该算法在路径构建过程中优先满足查询关键词的全包含条件，以关键词引导下的路径拓展替代盲目的邻边拓展，从而高效地构建候选路径；通过变量缩放与无效路径裁剪，将问题求解复杂度由阶乘级转化为多项式级，进一步降低算法复杂度，提升可扩展性。通过四组图数据集下的实验，验证了算法在查询效率与可扩展性上的提升
%K 基于关键词的最优路径查询
%K 复杂度
%K 可扩展性
%U http://www.joca.cn/CN/abstract/abstract20257.shtml