自从上世纪后期,数据挖掘就作为一种新兴且有效的信息提取手段,不断受到越来越多科学研究人员的重视和研究。图形挖掘作为数据挖掘学科的一个新兴的交叉领域是在2000年开始被一些专家学者提出并研究。图形挖掘本质上就是将数据挖掘技术推广到利用图形对领域和科研信息进行建模的科学研究中,并在此基础上研究出适合各个领域的新的图形挖掘技术,从而推动科研生产的发展。图形挖掘主要的应用领域,即化学和生物信息科学。在这些领域中利用图形对一些领域信息如分子,蛋白质链等进行建模,然后通过在相应的图形数据集中挖掘出一些对各种科学研究有价值的模式信息,来为科学研究服务。频繁子图挖掘和图形相似性搜索是图形挖掘中两个重要的研究领域。频繁子图挖掘,即从给定图形数据集中挖掘频繁出现的一些子图或图(也叫子结构或模式)。而这些频繁子图(模式)实质上就表示相关领域的一些重要的信息。图形相似性搜索,即在给定的基于领域信息建模的图形数据集中查询满足某种相似性条件的图形,是在2004年才由Yan等人提出。这种搜索广泛应用于各种科学研究中,如新药物的研制,化合物毒性的预测等。近似图包含搜索作为一种图形相似性搜索最早是在2007年Chen等人的关于图包含搜索的论文中被提出,但并没有研究。这之前的研究只局限与精确搜索和传统子结构相似性搜索。传统子结构相似性搜索,即查询给定数据集中包含或近似包含给定查询图的模型图。近似图包含则是搜索被查询图包含或近似包含的模型图。由于包含关系截然相反,因此以前的针对传统子结构相似性搜索的索引构造策略对近似图包含搜索不再适用,并且,在此之前,还没有针对近似图包含搜索的索引构造算法提出。本文在对一些典型的关于频繁子图挖掘和图形相似性搜索的索引构造算法进行充分研究的基础上,提出了一种基于覆盖率和支持度的针对近似图包搜索的索引构造算法csIndex(coverage and support based Index),csIndex的主要思想是首先对从给定模型图集合中挖掘出的频繁子结构的覆盖率和支持度进行综合考查,并计算出其基于覆盖率和支持度的综合筛选能力,然后选择综合筛选能力较高的子结构作为索引项,并且将这些索引项组织成索引矩阵来建立索引系统。通过在一些该领域经典的实验和测试数据集上的各种测试,结果表明,csIndex能在完成高效的近似图包含搜索的同时有效避免子图同构测试,而子图同构测试已经证明属于NP完全问题。