从图数据库中挖掘频繁跳跃模式

被引：9

作者：

刘勇

李建中

高宏

机构：

[1] 哈尔滨工业大学计算机科学与技术学院

来源：

软件学报 | 2010年 / 21卷 / 10期

关键词：

数据挖掘; 图挖掘; 图数据库; 频繁子图; 跳跃模式;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

很多频繁子图挖掘算法已被提出.然而,这些算法产生的频繁子图数量太多而不能被用户有效地利用.为此,提出了一个新的研究问题:挖掘图数据库中的频繁跳跃模式.挖掘频繁跳跃模式既可以大幅度地减少输出模式的数量,又能使有意义的图模式保留在挖掘结果中.此外,跳跃模式还具有抗噪声干扰能力强等优点.然而,由于跳跃模式不具有反单调性质,挖掘它们非常具有挑战性.通过研究跳跃模式自身的特性,提出了两种新的裁剪技术:基于内扩展的裁剪和基于外扩展的裁剪.在此基础上又给出了一种高效的挖掘算法GraphJP(an algorithm for mining jump patterns from graph databases).另外,还严格证明了裁剪技术和算法GraphJP的正确性.实验结果表明,所提出的裁剪技术能够有效地裁剪图模式搜索空间,算法GraphJP是高效、可扩展的.

引用

页码：2477 / 2493

页数：17

共 14 条

[1] FOGGER:An algorithm for graph generator discovery. Zeng Z,Wang J,Zhang J,Zhou L. Proceedings of the12thInter-national Conference on Extending Database Technology . 2009
[2] Frequent subgraph discovery. Kuramochi M,Karypis G. Proc.of the1st IEEE Int’l Conf.on Data Mining . 2001
[3] Mining molecular fragments:Finding relevant substructures of molecules. Borgelt C,Berhold MR. Proc.of the2nd IEEE Int’l Conf.on Data Mining . 2002
[4] Efficient mining of frequent subgraphs in the presence of isomorphism. Huan J,Wang W,Prins J. Proc.of the3rd IEEE Int’l Conf.Data Mining . 2003
[5] A quickstart in frequent structure mining can make a difference. Nijssen S,Kok JN. Proc.of the10th ACM SIGKDD Int’l Conf.on Knowledge Discovery and Data Mining . 2004
[6] Closegraph:Mining closed frequent graph patterns. Yan X,Han J. Proc.of the9th ACM SIGKDD Int’l Conf.on Knowledge Discovery and Data Mining . 2003
[7] Spin:Mining maximal frequent subgraphs from graph databases. Huan J,Wang W,Prins J,Yang J. Proc.of the10th ACM SIGKDD Int’l Conf.on Knowledge Discovery and Data Mining . 2004
[8] Margin:Maximal frequent subgraph mining. Thomas LT,Valluri SR,Karlapalem K. Proc.of the6th IEEE Int’l Conf.Data Mining . 2006
[9] http://dtp.nci.nih.gov/docs/aids/searches/list.html .
[10] Adaptive parallel graph mining for CMP architectures. Chen YK. Proc.of the6th IEEE Int’l Conf.Data Mining . 2006

← 1 2 →