Graph indexing: a frequent structure-based approach
Graph indexing: a frequent structure-based approach
复制标题
DOI：
10.1145/1007568.1007607
复制
发表时间：
2004-06
期刊：
影响因子：
--
通讯作者：
Xifeng Yan;Philip S. Yu;Jiawei Han
中科院分区：
文献类型：
--
作者：
Xifeng Yan;Philip S. Yu;Jiawei Han
图在复杂结构和无模式数据（例如蛋白质、化合物和 XML 文档）建模中变得越来越重要。给定图形查询，希望通过基于图形的索引从大型数据库中快速检索图形。在本文中，我们研究了索引图的问题，并通过应用图挖掘技术提出了一种新颖的解决方案。与现有的基于路径的方法不同，我们的方法称为 gIndex，利用频繁子结构作为基本索引特征。频繁子结构是理想的候选者，因为它们探索数据的内在特征并且对于数据库更新相对稳定。为了减小索引结构的大小，引入了大小增加支持约束和判别性片段两种技术。我们的性能研究表明，与典型的基于路径的方法 GraphGrep 相比，gIndex 的索引大小小了 10 倍，但性能提高了 3--10 倍。 gIndex 方法不仅为图索引问题提供了优雅的解决方案，而且还演示了数据库索引和查询处理如何从数据挖掘（尤其是频繁模式挖掘）中受益。此外，这里开发的概念也可以应用于索引序列、树和其他复杂结构。
Graph has become increasingly important in modelling complicated structures and schemaless data such as proteins, chemical compounds, and XML documents. Given a graph query, it is desirable to retrieve graphs quickly from a large database via graph-based indices. In this paper, we investigate the issues of indexing graphs and propose a novel solution by applying a graph mining technique. Different from the existing path-based methods, our approach, called gIndex, makes use of frequent substructure as the basic indexing feature. Frequent substructures are ideal candidates since they explore the intrinsic characteristics of the data and are relatively stable to database updates. To reduce the size of index structure, two techniques, size-increasing support constraint and discriminative fragments, are introduced. Our performance study shows that gIndex has 10 times smaller index size, but achieves 3--10 times better performance in comparison with a typical path-based method, GraphGrep. The gIndex approach not only provides and elegant solution to the graph indexing problem, but also demonstrates how database indexing and query processing can benefit form data mining, especially frequent pattern mining. Furthermore, the concepts developed here can be applied to indexing sequences, trees, and other complicated structures as well.