Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (2): 352-359.DOI: 10.11772/j.issn.1001-9081.2017.02.0352

Previous Articles     Next Articles

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

JIN Pengfei, NIU Baoning, ZHANG Xingzhong   

  1. College of Computer Science and Technology, Taiyuan University of Technology, Taiyuan Shanxi 030024, China
  • Received:2016-08-12 Revised:2016-09-11 Online:2017-02-10 Published:2017-02-11
  • Supported by:

    This work is partially supported by the National Natural Science Foundation of China (61572345), the National Key Technology R&D Program (2015BAH37F01).


金鹏飞, 牛保宁, 张兴忠   

  1. 太原理工大学 计算机科学与技术学院, 太原 030024
  • 通讯作者: 张兴忠,
  • 作者简介:金鹏飞(1992-),男,浙江杭州人,硕士研究生,主要研究方向:空间数据查询;牛保宁(1964-),男,山西太原人,教授,博士,CCF高级会员,主要研究方向:大数据、数据库系统的自主计算与性能管理;张兴忠(1964-),男,山西太原人,副教授,硕士,主要研究方向:网络与多媒体、嵌入式系统。
  • 基金资助:



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.

Key words: keyword-aware optimal route query, complexity, scalability



关键词: 基于关键词的最优路径查询, 复杂度, 可扩展性

CLC Number: