期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

子图同构验证算法OES 被引量：3

OES:Subgraph Isomorphism Verification Algorithm
在线阅读 下载PDF
导出
摘要 提出一种新的子图同构验证算法OES,采用逐条边验证的方法寻找子图同构映射,以确定查询图是否为某个数据图的子图,通过调整边的验证顺序,提高算法的执行效率。给出一种为查询图的边打分的方法,每条边的得分越低,表明其剪枝效率越高,按照分数由低到高的边序验证可以取得较好的验证效率。 This paper proposes a novel subgraph isomorphism verification algorithm named OES, which tries to find a subgraph isomorphism map by searching edge by edge in order to check whether a query graph is contained in some data graphs, and it can raise the verification efficiency by adjusting the edge order. A grading method for edges in query graph is provided, in which the lower score an edge gets, the higher pruning efficiency it can gain. So that good efficiency can be gained by verifying the edges in the order from higher grades to lower grades.
作者 解春欣 汪卫
机构地区 复旦大学计算机科学技术学院
出处 《计算机工程》 CAS CSCD 北大核心 2011年第3期30-32,共3页 Computer Engineering
基金 国家自然科学基金资助项目"图数据库管理系统关键技术研究"(60673133)
关键词 子图查询 子图同构算法 查询优化 OES算法 subgraph query subgraph isomorphism algorithm query optimization OES algorithm
分类号 TP311.13 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献5

  • 1黄崇本,陶剑文.一种新颖的对比子图索引算法[J].计算机工程,2009,35(5):64-67. 被引量：2
  • 2Giugno R,Shasha D.Graphgrep:A Fast and Universal Method for Querying Graphs[C]//Proc.of ICPR'02.Quebec,Canada:[s.n.],2002:112-115.
  • 3Yan Xifeng,Yu Philip,Han Jiawei.Graph Indexing:A Frequent Structure-based Approach[C]//Proc.of SIGMOD'04.Paris,France:[s.n.],2004:335-346.
  • 4Ullman J R.An Algorithm for Subgraph Isomorphism[J].Journal of the ACM,1976,23(1):31-42.
  • 5Shang Haichuan,Zhang Ying,Lin Xuemin,et al.Taming Verification Hardness:An Effcient Algofithm for Testing Subgraph Isomorphism[C]//Proc.of VLDB'08.Auckland,New Zealand:[s.n.],2008:364-375.

二级参考文献7

  • 1Yan Xifeng, Yu P S, Han Jiawei. Graph Indexing: A Frequent Structure-based Approach[C]//Proc. of the ACM SIGMOD'04. Maison de la Chimie, Pads, France: ACM Press, 2004: 335-346.
  • 2Dong Guozhu, Li Jiny'an. Efficient Mining of Emerging Patterns: Discovering Trends and Differences[C]//Proc. of the 5th ACM SIGKDD. New York, USA: ACM Press, 1999: 43-52.
  • 3Ting R M H, Bailey J. Mining Minimal Contrast Subgraph Patterns[C]//Proc. of the 6th SIAM. Atlanta, Georgia, USA: ACM Press, 1999.
  • 4Shasha D, Wang J T L, Giugno R. Algorithmics and Applications of Tree and Graph Searching[C]//Proc. of the 21st ACM SIGMOD-SIGACT-SIGART. Santa Barbara, California, USA: ACM Press. 2002: 39-52.
  • 5Kuramochi M, Karypis G. Frequent Subgraph Discovery[C]//Proc. of the IEEE ICDM'01. San Jose, California, USA: IEEE Press,2001: 313-320.
  • 6Nijssen S, Kok J N. A Quickstart in Frequent Structure Mining Can Make a Difference[C]//Proc. of KDD'04. Seattle, WA, USA: ACM Press, 2004: 647-652.
  • 7Yan Xifeng, Han Jiawei. Closegraph: Mining Closed Frequent Graph Pattems[C]//Proc. of ACM SIGKDD'03. Washington D. C., USA: ACM Press, 2003: 286-295.

共引文献1

同被引文献31

  • 1赵宏伟,张海龙,刘萍萍,王慧,徐震宇.基于表象式语义网络的图匹配算法[J].吉林大学学报（工学版）,2008,38(S1):145-149. 被引量：1
  • 2Greenberg A, Jain N, Kandula S, et al. VL2.. A Sealable and Flexible Data Center Network[C]//Proe of SIGCOMM 2009. NJ : ACM, 2009 : 51-62.
  • 3Mysore R N, Pamboris A, Farrington N, et al. PortLand: A Scala- ble Fault-Tolerant Layer 2 Data Center Network Fabrie[C] // Proe of SIGCOMM2009. NJ : ACM, 2009 : 39-50.
  • 4GuoC, Wu H, Tan K, et al. DCelI: A Sealable and Fault Tole- rant Network Structure for Data Centers [C] // Proe of SIG- COMM 2008. NJ : ACM, 2008 : 75-86.
  • 5Guo C, Lu G, Li D, et al. BCube: A High Performance, Server eentric Network Architecture for Modular Data Centers[C] // SIGCOMM 2009. NJ: ACM, 2009 : 63-74.
  • 6Kerravala Z. As the value of enterprise networks escalates, so does the need for configuration management[R]. Boston: The Yankee Group, 2004.
  • 7Chen Kai, Guo Chuan-xiong, Wu Hai-tao, et al. DAC: Generic and Automatic Address Configuration for Data Center Networks [C]//Proc of SIGCOMM 2010. NJ:ACM,2010:84-99.
  • 8Rodeheffer T,Thekkath C, Anderson D. Smart Bridge: A seala- ble bridge architecture[C]//Proc of SIGCOMM 2000. NJ:ACM 2000:201-211.
  • 9Myers A, Ng E, Zhang H. Rethinking the service model:scaling Ethernet to a million nodes[C]//Proc of Hot Nets 2004. NJ: ACM, 2004: 87-100.
  • 10Perlman R. Rbridges:Transparent routing [C]//Proc of Infocom 2004. NJ : IEEE, 2004:105-118.

引证文献3

二级引证文献1

计算机工程
2011年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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