期刊文献+

面向子图同构的高效索引构建算法

High-efficiency data-graph-index construction algorithm for subgraph isomorphism problem
下载PDF
导出
摘要 针对子图同构中索引构建方法效率低、内存占用大而影响查询效率的问题,本文提出基于2次排序查找等价顶点的数据图索引构建算法。该算法采用不同邻接链表表示类别不同的语法等价顶点的邻居集合,并依此设计2次排序的方法快速查找数据图中两两互连和两两互不相连的等价顶点,然后依据语法等价和语法包含关系为数据图构建索引来提高子图同构查询的效率。最后,基于不同规模的数据集,通过实验验证了本文提出索引构建算法的高效性和可扩展性。 Considering the poor querying efficiency of existing subgraph isomorphism algorithms,due to the low efficiency and overhead memory usage at the time the index was being constructed,in this paper,we propose a datagraph-index construction algorithm based on double sorting to search for equivalent vertices.The algorithm uses different adjacency lists to represent neighbor vertex sets based on different types of syntactic equivalence between vertices.It then uses double sorting to search for equivalent vertices that are connected with and disconnected from each other,then constructs a data graph index based on the relationship between the syntactic equivalence and the syntactic containment.The experimental results on different scale data sets show that,compared with existing methods,the proposed algorithm reduces the index size and enhances the speed of index construction,thereby improving the efficiency of subgraph isomorphic queries.
作者 陈伟 李美云 陈子阳 罗雅琴 CHEN Wei;LI Meiyun;CHEN Ziyang;LUO Yaqin(School of Information Science and Engineering,Yanshan University,Qinhuangdao 066004,China;Department of Information Engineering,Hebei University of Environmental Engineering,Qinhuangdao 066102,China;School of Mathematics,Physicals and Statistics,Shanghai University of Engineering Science,Shanghai 201620,China)
出处 《哈尔滨工程大学学报》 EI CAS CSCD 北大核心 2019年第3期548-554,共7页 Journal of Harbin Engineering University
基金 国家自然科学基金项目(61472339 61572421)
关键词 子图同构 图索引 语法等价 语法包含 超图 排序 subgraph isomorphism data graph index syntactic equivalence syntactic containment hypergraph sort
  • 相关文献

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部