基于2-hop优化的子图模式匹配算法  

2-hop based for pattern matching algorithm on DAGS

作　　者：张航[1] 王宏志[1] 李建中[1] 高宏[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《黑龙江大学自然科学学报》2010年第1期78-82,共5页Journal of Natural Science of Heilongjiang University

基　　金：国家重点基础研究发展计划973项目(2006CB303000);国家自然基金重点资助项目(60533110);国家自然科学基金资助项目(60703012;60773063);黑龙江省青年科技专项资金(QC06C033);国家863计划资助项目(2009AA01Z149);NSFC/RGC联合科研基金(60831160525)

摘　　要：讨论大图上有效可达标记2-hop编码,及其构造的图结构信息数据结构在判定两点之间可达性的高效性,基于这些高效结构,提出一种基于栈的DAG全局图模式匹配算法,该算法结合了栈在匹配过程中线性空间开销的优势。实验结果表明,相对于目前主流的图模式匹配算法,该算法具有中间结果小,时间高效的优势。The high-performance reachability label 2-hop coding of large graph was discussed,as well as the time efficiency of 2-hop coding graph constructed structural information in the query reachability between two points.Based on these data stuction,presented a based stacks holistic twig pattern matching algorithm on,which combines advantages of linear space of the stacks.The test results showed that compared with the current matching algorithm,out algorithm outperforms well,which has a small intermediate results and time efficiency advantage.

关 键 词：子图查询 2-hop编码 整体图模式匹配 

分 类 号：TP274[自动化与计算机技术—检测技术与自动化装置]