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

Approximate subgraph query algorithm with result diversity

作　　者：洪佳明[1] 黄云 刘少鹏 印鉴[4] Hong Jiaming;Huang Yun;Liu Shaopeng;Yin Jian(School of Medical Information Engineering,Guangzhou University of Chinese Medicine,Guangzhou,510006,China;Software College,Jishou University,Zhangjiajie,427000,China;Department of Computer Science and Technology,Guangdong Polytechnic Normal University,Guangzhou,510665,China;School of Data and Computer Science,Sun Yat sen University,Guangzhou,510006,China)

机构地区：[1]广州中医药大学医学信息工程学院,广州510006 [2]吉首大学软件学院,张家界427000 [3]广东技术师范大学计算机科学学院,广州510665 [4]中山大学数据科学与计算机学院,广州510006

出　　处：《南京大学学报（自然科学版）》2019年第6期960-972,共13页Journal of Nanjing University（Natural Science）

基　　金：国家自然科学基金(61472453);广东省自然科学基金(2015A030310312);广东省教育厅青年创新人才项目(2017KQNCX117);广州中医药大学青年英才培养工程(QNYC20170204);广东省大数据分析与处理重点实验室开放基金(201802);广东大学生科技创新培育专项基金(pdjh2018a0289)

摘　　要：针对大型图中的各种top k近似子图查询算法存在的顶点重叠度高、无法满足多样性匹配结果输出等问题,提出具有最大顶点覆盖集的多样性近似子图查询算法.该算法建立基于近邻关系和基于区域划分的双重索引,并为相互关系紧密的同标号顶点建立簇索引.在图查询过程中,利用近邻特征为查询图中的每个顶点快速筛选出满足局部匹配要求的候选顶点集,并从不同区域找到多个满足要求的近似匹配子图,避免了查询结果间的高重复率.同时,基于区域和同标号近邻簇的划分,优先查找属于不同划分或不同簇顶点的匹配,减少了不同区域划分间的交互,提高了查询的效率.在大量数据集上的实验结果验证了该算法在查询效率和结果多样性等方面的有效性.This paper proposes a new algorithm for the diversified top k approximate subgraph query with maximum vertex cover set to avoid the typical problem of many state of the art algorithms that a large number of duplicate vertices might occur in the result set.The algorithm builds the double index based on the nearest neighbor relation and the region partition,and sets up the cluster index for the closely related vertices.In the process of graph query,we use the nearest neighbor feature to quickly select the candidate vertex set for each vertex in the query graph.We find multiple approximate matching subgraphs from different regions to avoid the high repetition rate between the query results.Meanwhile,based on the division of the region and the neighborhood vertices cluster,we process the graph query from different partitions or the different cluster vertices in order to reduce the interactions between different regions and improve the query efficiency.Extensive experiments on many datasets confirm the effectiveness of our new algorithm in query efficiency and result diversity.

关 键 词：子图查询 近似查询 结果多样性 顶点覆盖集 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]