杜明¹,杨云¹,周军锋¹,陈子阳²,杨安平¹

¹(东华大学计算机科学与技术学院 上海 201620);²(上海立信会计金融学院信息管理学院 上海 201620) (duming@dhu.edu.cn)

出版日期: 2020-09-01


基金资助:国家重点研发计划项目(2017YFB0309800)；国家自然科学基金项目(61472339,61572421,61873337)

Efficient Methods for Label-Constraint Reachability Query

Du Ming¹, Yang Yun¹, Zhou Junfeng¹, Chen Ziyang², Yang Anping¹

¹(School of Computer Science and Technology, Donghua University, Shanghai 201620);²(School of Information Management, Shanghai Lixin Institute of Accounting and Finance, Shanghai 201620)

Online: 2020-09-01


Supported by:This work was supported by the National Key Research and Development Program of China (2017YFB0309800) and the National Natural Science Foundation of China (61472339, 61572421, 61873337).

摘要/Abstract

摘要： 基于标签约束的可达性查询s→\-Lt用于回答给定图中顶点s到顶点t是否存在路径标签属于L的有向路径.针对现有方法索引构建时间长、索引规模大、查询效率低的问题，首先基于k个点构建双向路径标签索引，并提出相应的优化措施减小索引规模，以此来加速可达查询的处理速度.由于其索引没有完全覆盖可达查询，虽然索引规模小，但仍然无法避免查询过程中的图遍历操作.为此，进一步提出覆盖所有可达信息的双向路径标签索引，基于该索引，查询处理时可以完全避免图上的遍历操作.最后，基于多个真实数据集进行测试，实验结果从索引大小、索引构建时间和查询响应时间方面验证了所提方法相对现有方法具有索引规模小、索引时间短且查询响应快的优势.

参考文献

相关文章 7

[1]	张昕,李晓光. 流模式下有向近似覆盖图算法研究[J]. 计算机研究与发展, 2019, 56(3): 655-665.
[2]	王一舒,袁野,刘萌,王国仁. 大规模时序图数据的查询处理与挖掘技术综述[J]. 计算机研究与发展, 2018, 55(9): 1889-1902.
[3]	于静,刘燕兵,张宇,刘梦雅,谭建龙,郭莉. 大规模图数据匹配技术综述[J]. 计算机研究与发展, 2015, 52(2): 391-409.
[4]	张爱清,莫则尧,杨章. 数据驱动并行计算的3层软件架构设计及应用[J]. 计算机研究与发展, 2014, 51(11): 2538-2546.
[5]	曹 珲, 熊胜超, 张焕国, 严 飞,. Flume系统的隐蔽信道搜索问题研究[J]. , 2013, 50(11): 2367-2374.
[6]	曹 佳, 鲁士文,. 关于覆盖组播中拓扑发现的研究[J]. , 2006, 43(5): 784-790.
[7]	文中华, 姜云飞,. 用分层关联方法求有向图中所有Hamilton回路的算法[J]. , 2005, 42(10): 1809-1814.

PDF全文下载地址:

https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=4260