1. 中山大学信息科学与技术学院,广东,广州,510006
2. 吉首大学软件服务外包学院,湖南,张家界,427000
3. 广州中医药大学医学信息工程学院,广东,广州,510006
4. 中山大学信息科学与技术学院,广东,广州,510006
5. 吉首大学软件服务外包学院,湖南,张家界,427000
6. 广州中医药大学医学信息工程学院,广东,广州,510006
网络出版:2017-02-25,
纸质出版:2017
移动端阅览
黄云, 洪佳明, 覃遵跃, 等. ERSearch:一种高效的子图查询算法[J]. 电子学报, 2017,45(2):368-375.
HUANG Yun, HONG Jia-ming, QIN Zun-yue, et al. ERSearch: An Efficient Subgraph Query Algorithm[J]. Acta Electronica Sinica, 2017, 45(2): 368-375.
黄云, 洪佳明, 覃遵跃, 等. ERSearch:一种高效的子图查询算法[J]. 电子学报, 2017,45(2):368-375. DOI: 10.3969/j.issn.0372-2112.2017.02.015.
HUANG Yun, HONG Jia-ming, QIN Zun-yue, et al. ERSearch: An Efficient Subgraph Query Algorithm[J]. Acta Electronica Sinica, 2017, 45(2): 368-375. DOI: 10.3969/j.issn.0372-2112.2017.02.015.
子图查询是图数据库研究中的一个重要问题,许多方法基于过滤-验证策略进行子图查询,算法研究的重点为快速找到有效的特征集.通过对特征模式在数据图集中的嵌入信息进行分析,离线建立基于重叠关系、邻接关系和近邻关系的嵌入关系索引,提出基于嵌入关系的子图查询算法ERSearch.在给定查询图后,利用特征共现关系与特征嵌入关系联合进行过滤操作,并将过滤阶段的嵌入关系比对结果用于验证过程,提高验证效率.在真实及模拟数据上的实验表明,通过与PathIndex等方法的对比,ERSearch算法有效缩减了候选集的规模,能有效提高过滤与验证阶段的执行效率.
Subgraph query is an important problem in the research of graph databases
and many methods about subgraph query are based on filtering-verification strategy
which key target is to find effective feature patterns.Through the analysis of the embedding information of feature patterns in the data graphs
we propose to construct embedding relation indexing in the offline stage
and propose a new feature pattern embedding based subgraph query algorithm ERSearch.When query graph is given
we will use the co-occurrence relations and embedding relations combined to prune the unmatched data graphs
and the comparing results of embedded relationship in filtering phase can be used in the verification process
improving the efficiency of the verification.Via the experiment in the real and synthetic datasets
compared with PathIndex and other methods
we show that our algorithm can effectively reduce the size of candidate set
and effectively improve the efficiency of filtering and verification stages.
0
浏览量
19
下载量
2
CSCD
关联资源
相关文章
相关作者
相关机构
京公网安备11010802024621