ERSearch:一种高效的子图查询算法
发布时间：2019-04-08 12:14
【摘要】：子图查询是图数据库研究中的一个重要问题,许多方法基于"过滤-验证"策略进行子图查询,算法研究的重点为快速找到有效的特征集.通过对特征模式在数据图集中的嵌入信息进行分析,离线建立基于重叠关系、邻接关系和近邻关系的嵌入关系索引,提出基于嵌入关系的子图查询算法ERSearch.在给定查询图后,利用特征共现关系与特征嵌入关系联合进行过滤操作,并将过滤阶段的嵌入关系比对结果用于验证过程,提高验证效率.在真实及模拟数据上的实验表明,通过与PathIndex等方法的对比,ERSearch算法有效缩减了候选集的规模,能有效提高过滤与验证阶段的执行效率.
[Abstract]:Subgraph query is an important problem in the research of graph database. Many methods perform subgraph query based on "filter-verify" strategy. The focus of algorithm research is to find effective feature sets quickly. By analyzing the embedding information of feature pattern in the data set, the embedding relation index based on overlapping relation, adjacency relation and nearest neighbor relation is established offline, and a subgraph query algorithm ERSearch. based on embedded relation is proposed. After the query graph is given, the feature co-occurrence relation and the feature embedding relation are combined to carry out the filtering operation, and the results of the comparison of the embedding relations in the filtering stage are used in the verification process to improve the verification efficiency. Experiments on real and simulated data show that, by comparing with PathIndex and other methods, ERSearch algorithm can effectively reduce the size of candidate sets and improve the efficiency of filtering and verification.
【作者单位】： 中山大学信息科学与技术学院;吉首大学软件服务外包学院;广州中医药大学医学信息工程学院;
【基金】：国家自然科学基金(No.61033010,No.61272065,No.61472453) 广东省自然科学基金(No.S2011020001182,No.2014A030309013) 广东省科技计划基金(No.2009B090200450,No.2010A040303004,No.2011B040200007) 广东省医学科研基金(No.B2014174)
【分类号】：TP311.13
[Abstract]:Subgraph query is an important problem in the research of graph database. Many methods perform subgraph query based on "filter-verify" strategy. The focus of algorithm research is to find effective feature sets quickly. By analyzing the embedding information of feature pattern in the data set, the embedding relation index based on overlapping relation, adjacency relation and nearest neighbor relation is established offline, and a subgraph query algorithm ERSearch. based on embedded relation is proposed. After the query graph is given, the feature co-occurrence relation and the feature embedding relation are combined to carry out the filtering operation, and the results of the comparison of the embedding relations in the filtering stage are used in the verification process to improve the verification efficiency. Experiments on real and simulated data show that, by comparing with PathIndex and other methods, ERSearch algorithm can effectively reduce the size of candidate sets and improve the efficiency of filtering and verification.
【作者单位】： 中山大学信息科学与技术学院;吉首大学软件服务外包学院;广州中医药大学医学信息工程学院;
【基金】：国家自然科学基金(No.61033010,No.61272065,No.61472453) 广东省自然科学基金(No.S2011020001182,No.2014A030309013) 广东省科技计划基金(No.2009B090200450,No.2010A040303004,No.2011B040200007) 广东省医学科研基金(No.B2014174)
【分类号】：TP311.13
【相似文献】
相关期刊论文 前10条
1 王映龙;杨s，
本文编号：2454565
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2454565.html
