分布式Top-k子图匹配技术

• 作者: 兰超 张勇 邢春晓
• 来源期刊: 清华大学学报（自然科学版）
• 学科: 工学
• 关键词: 图搜索 子图匹配 Top-k 子图匹配 分布式
• 年，卷（期）: 2016,（8）
• 所属期刊栏目: 计算机科学与技术
• 页码范围: 871-877
• 页数: 7页
• 分类号: TP319
• 语种: 中文
• DOI: 10.16511/j.cnki.qhdxxb.2016.25.026

摘要

Top-k子图匹配是一种应用广泛的图搜索技术.相比于单机环境,分布式环境下的Top-k子图匹配问题具有更大的挑战性.该文分析了已有方法在分布式环境下存在的问题,提出了包括查询拆分、查询执行、结果连接3个步骤的算法.算法通过查询拆分,彻底避免了生成中间结果过程中的数据传输,同时通过优化查询执行和结果连接步骤,避免不必要的中间结果生成,降低单个节点的计算量,提升整体效率.在此基础上,该文对分布式环境下Top-k连接策略进行了进一步优化.在真实图数据上进行的实验测试表明:该文提出的算法能够有效解决分布式环境下Top-k子图匹配问题,具有很好的扩展性,而且使用优化连接策略的算法性能较基础算法的效率有明显的提升.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张勇		121	1865	23.0	40.0
2	邢春晓		84	2349	18.0	47.0
3	兰超		3	5	1.0	2.0