具有结果多样性的近似子图查询算法

• 作者: 刘少鹏 印鉴 洪佳明 黄云
• 来源期刊: 南京大学学报（自然科学版）
• 学科: 工学
• 关键词: 子图查询 近似查询 结果多样性 顶点覆盖集
• 年，卷（期）: 2019,（6）
• 页码范围: 960-972
• 页数: 13页
• 分类号: TP311
• 字数: 11293字
• 语种: 中文
• DOI: 10.13232/j.cnki.jnju.2019.06.009

摘要

针对大型图中的各种top-k近似子图查询算法存在的顶点重叠度高、无法满足多样性匹配结果输出等问题,提出具有最大顶点覆盖集的多样性近似子图查询算法.该算法建立基于近邻关系和基于区域划分的双重索引,并为相互关系紧密的同标号顶点建立簇索引.在图查询过程中,利用近邻特征为查询图中的每个顶点快速筛选出满足局部匹配要求的候选顶点集,并从不同区域找到多个满足要求的近似匹配子图,避免了查询结果间的高重复率.同时,基于区域和同标号近邻簇的划分,优先查找属于不同划分或不同簇顶点的匹配,减少了不同区域划分间的交互,提高了查询的效率.在大量数据集上的实验结果验证了该算法在查询效率和结果多样性等方面的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	印鉴	中山大学数据科学与计算机学院	117	2906	26.0	51.0
2	黄云	吉首大学软件学院	46	769	7.0	27.0
3	洪佳明	广州中医药大学医学信息工程学院	8	58	3.0	7.0
4	刘少鹏	广东技术师范大学计算机科学学院	2	1	1.0	1.0