SCBT-index:基于谱编码的子图索引算法

• 作者: 施炜杰 董一鸿 辛宇 钱江波 陈华辉
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 谱编码 Gini系数 子图查询 子图索引
• 年，卷（期）: 2020,（1）
• 所属期刊栏目: 学术论文
• 页码范围: 110-117
• 页数: 8页
• 分类号: TP393
• 字数: 5998字
• 语种: 中文
• DOI: 10.3969/j.issn.0372-2112.2020.01.013

摘要

随着图模型规模的扩大,单机算法难以适应大规模数据集下的子图查询.而现有的分布式算法基于无索引的简单遍历,join过程容易出现内存溢出,而且查询图分布异常时易出现负载不均衡.提出了一种基于谱编码的二叉索引树(SCBT-index),首先对数据图中的顶点谱编码,根据编码信息构建二叉索引树.然后对查询图使用最小查询计划进行分解,最后join过程使用3个剪枝策略:基于拓扑结构的预剪枝、序列化join和基于分布式下的join优化.实验结果表明,SCBT-index在图集下的综合性能优于现有主流算法,单图下的查询时间为现有算法的1/2到1/4.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	钱江波	宁波大学信息科学与工程学院	54	202	8.0	11.0
2	董一鸿	宁波大学信息科学与工程学院	55	224	8.0	13.0
3	陈华辉	宁波大学信息科学与工程学院	63	319	9.0	15.0
4	辛宇	宁波大学信息科学与工程学院	4	0	0.0	0.0
5	施炜杰	宁波大学信息科学与工程学院	4	0	0.0	0.0