期刊文献+

基于信息熵的子图匹配算法 被引量:1

Information entropy based algorithm for efficient subgraph matching
下载PDF
导出
摘要 子图查询是指输入一个图数据库和查询子图,输出图数据库中包含查询子图的图集合,它广泛应用于社会网、生物网和信息网的查询应用中。目前的子图查询算法大多采用静态消耗测算模式,此类测算模式在图中点数和连接边数呈指数分布时,会在少数节点上花费较多时间遍历其邻节点,导致查询算法效率低下。根据信息熵在信息度量中的作用,将条件信息熵作为启发式匹配的依据,提出了基于信息熵的子图匹配算法。实验表明,基于信息熵的子图匹配算法具有更高的查询效率,且在指数分布的数据集上效果更明显。 Subgraph matching query refers to input a query graph and a data graph,and output the graph which contains all the subgraphs of the data graph.Subgraph query is widely used in social network,biological network and the query application of the information network.Current work on subgraph matching queries used static cost models which could be ineffective due to long-tailed degree distributions,for it would spend more time in traversing the adjacent node.According to the information entropy on the basis of information measure,using the conditional information entropy as the basic for the heuristic matching subgraph matching algorithm,this paper proposed an information entropy based algorithm for efficient subgraph matching.Experiments show that the proposed method has a higher efficiency of inquires.And in the long-tailed degree distributions of dataset,the effect is more apparent.
出处 《计算机应用研究》 CSCD 北大核心 2012年第11期4035-4037,共3页 Application Research of Computers
基金 国家自然科学基金资助项目(71003096 61003169) 高等学校博士学科点专项科研基金资助项目(20110095110010 20100095110003)
关键词 图数据 信息熵 子图匹配 graph information entropy subgraph matching query
  • 引文网络
  • 相关文献

参考文献13

  • 1GAREY M R, JOLMSON D S. Computers and intaetbility:a guide to the theory of NP-completeness [ M ]. New York : W H Freeman &Co, 1990.
  • 2KETKAR S, HOLDER B, COOK J. Subdue: compression-based frequent pattern discovery[ C ]//Proc of ACM KDD Workshop on Opensource Data Mining. 2005:71-76.
  • 3ULLMAN J R. An algorithm for subgraph isomorphism[ J]. Journal of the ACM,1976,23( 1 ) :31-42.
  • 4McKAY B D. Practical graph isomorphism[ J]. Congressus Numerantium, 1981:45-87.
  • 5L CORDELLA, P. FOGGIA, C. SANSONE, M. VENTO. A (sub) graph isomorphism algorithm for matching Iarge graphs [ J ]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2004,26 ( 10 ) : 1367-1372.
  • 6SHANG Hai-chuan, ZHANG Y, LIN X, et al. Taming verification hardness: an efficient algorithm for testing subgraph isomorphism [ C ]//Proc of International Conference on Very Large Data Bases. 2008:364- 375.
  • 7BROCHELER M, PUGLIESE A, SUBRAHMANIAN V S. A budgetbased algorithm for efficient subgraph matching on huge networks [ C ]//Proc of the 27th International Conference on Data Engineering. Washington DC : IEEE Computer Society,2011:94- 99.
  • 8MAHMOUDINASAB H, SAKR S. An experimental evaluation of relational rdf storage and querying techniques [ C ]//Proc of the 15th International Conference on Database Systemfor Advanced Applications. Bedin : Springer-Verlag,2010 : 215- 226.
  • 9CHENG J, KE Y, NG W. Efficient query processing on graph databases [ J ]. ACM Trans on Database System,2009:34 ( 1 ).
  • 10GIUGNO R, SHASHA D. GraphGrep:a fast and universal method for querying graphs [ C ]//Proc of the 16th International Conference on Pattern Recognition. 2002 : 112-115.

同被引文献4

引证文献1

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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