高效的多关键词匹配最优路径查询算法KSRG

KSRG:an efficient optimal route query algorithm for multi-keyword coverage

为改进基于关键词的最优路径查询算法,在大规模图以及多查询关键词下复杂度过高与可扩展性不足的缺陷,依据查询关键词序列构建候选路径的策略提出一种高效查询算法。该算法在路径构建过程中优先满足查询关键词的全包含条件,以关键词引导下的路径拓展替代盲目的邻边拓展,从而高效地构建候选路径;通过变量缩放与无效路径裁剪,将问题求解复杂度由阶乘级转化为多项式级,进一步降低算法复杂度,提升可扩展性。通过四组图数据集下的实验,验证了算法在查询效率与可扩展性上的提升。

To alleviate the issues of high complexity and poor scalability in the processing of keyword-aware optimal route query algorithms for large scale graph or multiple query keywords, an effective algorithm was proposed based on the scheme of keyword sequence route generating. The algorithm satisfied the coverage of query keywords first, and took a path expansion inspired by the keyword coverage property rather than aimless adjacent edge expansion to efficiently construct candidate paths. With the aid of a scaling method and ineffective route pruning, the search space was reduced into a polynomial order from an original factorial order, which further reduced the complexity and enhanced the scalability. Experiments conducted over four gragh datasets verified the accuracy and improvement in efficiency and scalability of the proposed algorithm.