Scalable mining of large disk-based graph databases
Scalable mining of large disk-based graph databases
复制标题
DOI：
10.1145/1014052.1014088
复制
发表时间：
2004-08
期刊：
影响因子：
--
通讯作者：
Chen Wang;Wei Wang;J. Pei;Yongtai Zhu;Baile Shi
中科院分区：
文献类型：
--
作者：
Chen Wang;Wei Wang;J. Pei;Yongtai Zhu;Baile Shi
从图数据库中挖掘频繁的结构模式是广泛应用中一个有趣的问题。以前的大多数研究都集中在有效地修剪无效的搜索子空间，但很少涉及大型基于磁盘的数据库的挖掘。由于应用程序中的许多图形数据库无法保存在主内存中，因此基于磁盘的大型图形数据库的可扩展挖掘仍然是一个具有挑战性的问题。在本文中，我们开发了一种有效的索引结构，ADI（用于邻接索引），以支持在无法保存到主内存中的大型数据库上挖掘各种图形模式。该索引构建简单、高效。此外，新的索引结构可以很容易地应用于各种现有的图模式挖掘算法中。作为示例，我们使用 ADI 结构来改编著名的 gSpan 算法。实验结果表明，新的索引结构使得能够在大型数据库上进行可扩展的图模式挖掘。在一组实验中，新的基于磁盘的方法可以挖掘具有100万张图的图数据库，而原始的gSpan算法只能处理最多30万张图的数据库。此外，当两者都可以在主内存中运行时，我们的新方法比 gSpan 更快。
Mining frequent structural patterns from graph databases is an interesting problem with broad applications. Most of the previous studies focus on pruning unfruitful search subspaces effectively, but few of them address the mining on large, disk-based databases. As many graph databases in applications cannot be held into main memory, scalable mining of large, disk-based graph databases remains a challenging problem. In this paper, we develop an effective index structure, ADI (for adjacency index), to support mining various graph patterns over large databases that cannot be held into main memory. The index is simple and efficient to build. Moreover, the new index structure can be easily adopted in various existing graph pattern mining algorithms. As an example, we adapt the well-known gSpan algorithm by using the ADI structure. The experimental results show that the new index structure enables the scalable graph pattern mining over large databases. In one set of the experiments, the new disk-based method can mine graph databases with one million graphs, while the original gSpan algorithm can only handle databases of up to 300 thousand graphs. Moreover, our new method is faster than gSpan when both can run in main memory.