ERSearch:一种高效的子图查询算法

ERSearch:An Efficient Subgraph Query Algorithm

子图查询是图数据库研究中的一个重要问题,许多方法基于"过滤-验证"策略进行子图查询,算法研究的重点为快速找到有效的特征集.通过对特征模式在数据图集中的嵌入信息进行分析,离线建立基于重叠关系、邻接关系和近邻关系的嵌入关系索引,提出基于嵌入关系的子图查询算法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 Pathlndex 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.