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

doi:10.11772/j.issn.1001-9081.2017.02.0352

计算机应用 ›› 2017, Vol. 37 ›› Issue (2): 352-359.DOI: 10.11772/j.issn.1001-9081.2017.02.0352

• 第33届中国数据库学术会议（NDBC 2016） • 上一篇下一篇

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

金鹏飞, 牛保宁, 张兴忠

太原理工大学计算机科学与技术学院, 太原 030024

收稿日期:2016-08-12 修回日期:2016-09-11 出版日期:2017-02-10 发布日期:2017-02-11
通讯作者: 张兴忠,zhangxingzhong@tyut.edu.cn
作者简介:金鹏飞(1992-),男,浙江杭州人,硕士研究生,主要研究方向:空间数据查询;牛保宁(1964-),男,山西太原人,教授,博士,CCF高级会员,主要研究方向:大数据、数据库系统的自主计算与性能管理;张兴忠(1964-),男,山西太原人,副教授,硕士,主要研究方向:网络与多媒体、嵌入式系统。
基金资助:
国家自然科学基金资助项目（61572345）；国家科技支撑计划项目（2015BAH37F01）。

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

JIN Pengfei, NIU Baoning, ZHANG Xingzhong

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).

摘要/Abstract

摘要：

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

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

Abstract:

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

中图分类号:

TP311

金鹏飞, 牛保宁, 张兴忠. 高效的多关键词匹配最优路径查询算法KSRG[J]. 计算机应用, 2017, 37(2): 352-359.

JIN Pengfei, NIU Baoning, ZHANG Xingzhong. KSRG: an efficient optimal route query algorithm for multi-keyword coverage[J]. Journal of Computer Applications, 2017, 37(2): 352-359.

参考文献

[1] RESNA R, LALLU A. Optimal route queries for road networks with user interest[J]. International Journal of Computer Trends and Technology, 2015, 21(1):41-45.
[2] CAO X, CHEN L, CONG G, et al. Keyword-aware optimal route search[J]. Proceedings of the VLDB Endowment, 2012, 5(11):1136-1147.
[3] CONG G, CHEN L, CAO X, et al. KORS:keyword-aware optimal route search system[C]//ICDE'13:Proceedings of the 2013 IEEE International Conference on Data Engineering. Washington, DC:IEEE Computer Society, 2013:1340-1343.
[4] CONG G, JENSEN C S. Querying geo-textual data:spatial keyword queries and beyond[C]//SIGMOD'16:Proceedings of the 2016 International Conference on Management of Data. New York:ACM, 2016:2207-2212.
[5] CONG G, JENSEN C S, WU D. Efficient retrieval of the top-k most relevant spatial Web objects[J]. Proceedings of the VLDB Endowment, 2009, 2(1):337-348.
[6] CAO X, CONG G, JENSEN C S, et al. Collective spatial keyword querying[C]//SIGMOD'11:Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2011:373-384.
[7] CHEN L, CONG G, JENSEN C S, et al. Spatial keyword query processing:an experimental evaluation[J]. Proceedings of the VLDB Endowment, 2013, 6(3):217-228.
[8] CHOUDHURY F M, CULPEPPER J S, SELLIS T, et al. Maximizing bichromatic reverse spatial and textual k nearest neighbor queries[J]. Proceedings of the VLDB Endowment, 2016, 9(6):456-467.
[9] CAO X, CONG G, JENSEN C S, et al. Retrieving regions of interest for user exploration[J]. Proceedings of the VLDB Endowment, 2014, 7(9):733-744.
[10] LI F F, CHENG D, HADJIELEFTHERIOU M, et al. On trip planning queries in spatial databases[C]//Proceedings of the 9th International Symposium on Advances in Spatial and Temporal Databases, LNCS 3633. Berlin:Springer-Verlag, 2005:273-290.
[11] SHARIFZADEH M, KOLAHDOUZAN M, SHAHABI C. The optimal sequenced route query[J]. The VLDB Journal, 2008, 17(4):765-787.
[12] CHEN H, KU W-S, SUN M-T, et al. The multi-rule partial sequenced route query[C]//GIS'08:Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York:ACM, 2008:Article No. 10.
[13] LI J, YANG Y, MAMOULIS N. Optimal route queries with arbitrary order constraints[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(5):1097-1110.
[14] 宋晓宇,许鸿斐,孙焕良,等.基于签到数据的短时间体验式路线搜索[J].计算机学报,2013,36(8):1693-1703. (SONG X Y, XU H F, SUN H L, et al. Short-term experience route search based on check-in data[J]. Chinese Journal of Computers, 2013, 36(8):1693-1703.).
[15] 鲍金玲,杨晓春,王斌,等.一种支持约束关系的高效的行程规划算法[J].小型微型计算机系统,2013,34(12):2702-2707. (BAO J L, YANG X C, WANG B, et al. An efficient trip planning algorithm under constraint[J]. Journal of Chinese Computer Systems,2013, 34(12):2702-2707.).
[16] CHEN Z, SHEN H T, ZHOU X. Discovering popular routes from trajectories[C]//ICDE'11:Proceedings of the 2011 IEEE 27th International Conference on Data Engineering. Washington, DC:IEEE Computer Society, 2011:900-911.
[17] FLOYD R W. Algorithm 97:shortest path[J]. Communications of the ACM, 1962, 5(6):345.
[18] CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to algorithms[M]. 3rd ed. Cambridge, MA:MIT Press, 2009:450-462.
[19] DUMITRESCU I, BOLAND N. Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem[J]. Networks, 2003, 42(3):135-153.
[20] ABEYWICKRAMA T, CHEEMA M A, TANIAR D. K-nearest neighbors on road networks:a journey in experimentation and in-memory implementation[J]. Proceedings of the VLDB Endowment, 2016, 9(6):492-503.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张鲁飞, 孙茹君, 秦芳. 面向图计算的运行时系统的消息聚合技术[J]. 计算机应用, 2021, 41(4): 984-989.
[2]	徐志强, 蒋铁钢, 杨立波. 基于随机支撑挑选的广义正交匹配追踪算法[J]. 计算机应用, 2020, 40(4): 1104-1108.
[3]	吴文莉, 刘国华, 张君宝. 大数据上函数查询解答的复杂度分析[J]. 计算机应用, 2020, 40(2): 416-419.
[4]	史志才, 王益涵, 张晓梅, 陈珊珊, 陈计伟. 可扩展及可证安全的射频识别认证协议[J]. 计算机应用, 2019, 39(3): 774-778.
[5]	陈婉杰, 盛益强. 基于网络表示学习的非单一维度的社区发现算法[J]. 计算机应用, 2019, 39(12): 3467-3475.
[6]	赵焜松, 余敦辉, 张万山. 软件众包任务发布优先级计算方法[J]. 计算机应用, 2018, 38(7): 2032-2036.
[7]	肖文, 胡娟. 基于数据集稀疏度的频繁项集挖掘算法性能分析[J]. 计算机应用, 2018, 38(4): 995-1000.
[8]	吴文燕, 姜鑫, 王晓锋, 刘渊. 虚拟化与数字仿真融合的多尺度网络复现技术[J]. 计算机应用, 2018, 38(3): 746-752.
[9]	余敦辉, 王意, 张万山. 软件众包工人能力动态度量算法[J]. 计算机应用, 2018, 38(12): 3612-3617.
[10]	周围, 郭梦雨, 向丹蕾. 空间调制系统下改进的QRD-M检测算法[J]. 计算机应用, 2018, 38(10): 2950-2954.
[11]	杭波, 王毅, 康长青. 移动音频带宽扩展算法计算复杂度优化[J]. 计算机应用, 2016, 36(2): 516-520.
[12]	李胜华, 赵晗诺, 罗炼飞. 大线性复杂度三值自相关的二元三阶分圆序列的构造[J]. 计算机应用, 2015, 35(9): 2542-2545.
[13]	韩国梁, 盛茂家, 包丛笑, 李星. IPv4网络与IPv6互联网的无状态通信机制[J]. 计算机应用, 2015, 35(8): 2113-2117.
[14]	彭新东, 杨勇. 区间值模糊软集的信息测度及其聚类算法[J]. 计算机应用, 2015, 35(8): 2350-2354.
[15]	郝彦彬, 郭晓, 杨乃定. 基于增量计算的信息系统属性粒结构计算方法[J]. 计算机应用, 2015, 35(7): 1915-1920.