基于参考节点嵌入的图可达性查询

• 作者: 曾亚光 林冬梅 温菊屏 胡小生
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: k步可达性查询 带距离约束的图可达性查询 参考节点嵌入 三角不等式关系 最短路径树
• 年，卷（期）: 2016,（7）
• 所属期刊栏目: 大数据
• 页码范围: 1998-2005,2045
• 页数: 9页
• 分类号: TP301.6
• 字数: 11365字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2016.07.1998

摘要

针对k步可达性查询算法无法解决带距离约束的图可达性查询问题,提出基于参考节点嵌入的图可达性查询算法.首先,从所有节点中选出极少数有代表性的全局参考节点,预先计算所有节点与全局参考节点之间的最短路径距离;然后,采用最短路径树和范围最小值查询技术求得局部参考节点;接着,利用三角不等式关系得到查询点对距离范围;最后,根据查询条件中的距离值与查询点对距离范围上、下限值的大小关系,可快速得出可达性结论.针对社会关系网络和公路网络数据,将所提算法与Dijkstra算法、K-Reach算法进行实验对比测试.相较于K-Reach算法,其索引建立时间小4个数量级,其索引规模小2个数量级;相较于Dijkstra算法,在公路网络和社会关系网络中,直接得出可达性结论的比例分别为92％和78.6％,其查询时间大大缩短,分别降低了95.5％和92％.实验结果表明:所提算法能够通过使用较小的索引开销,实现在线查询计算复杂度的降低,可很好地解决既适用于有权图又适用于无权图带距离约束的可达性查询问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	温菊屏	佛山科学技术学院电子与信息工程学院	10	65	4.0	8.0
3	林冬梅		38	213	7.0	13.0
5	胡小生	佛山科学技术学院电子与信息工程学院	19	198	7.0	14.0
7	曾亚光	佛山科学技术学院电子与信息工程学院	33	65	5.0	7.0