随着现代化信息技术的迅猛发展,人们对复杂事物建模的需求也越来越大。图作为一种能模拟复杂事物之间联系的数据结构在数据挖掘中显得越来越重要,表现在它能够表达更加丰富的语义和结构。目前,图已应用于很多领域,如化学领域、社会网络领域、模式匹配领域、XML领域等。图查询作为图数据集上的一个经典应用,从海量的图数据中获取用户想要的数据。目前,图查询策略主要是采用一种图数据库建立索引-过滤-精华提纯的过程,所以本文把对图索引的构造和过滤的研究作为研究重点。首先,本文介绍了图的相关基本概念、图查询算法的类型和图索引机制的算法分类,分别对基于结构的图索引算法和基于特征的图索引算法做了进一步地分析,归纳得出这些算法的优点和缺点,为图索引的建立奠定理论基础。其次,本文根据频繁图查询中遇到的问题,深刻研究了图查询的整个过程和图查询代价,提出了一种新的图索引算法。算法首先生成频繁子图的特征图,然后再对特征图进行分解,并验证特征图是否加入到无回路图中形成结点,最终分解得到的标准编码,再将这标准编码放入对应的哈希表里,并得出了最终的图索引结构。再次,本文提出了基于图特征索引的过滤算法,把图对边的放松查询转化为最大允许的损失特征数,利用特征聚合分层重新建立了图特征之间的关系,对特征集进行了分类排序,使得图查询过滤更加精确和高效。最后,本文通过实验对算法进行了验证,并将结果与现有算法做了对比,详细地分析了实验结果,进而验证了此算法的高效性和准确性。
本文来源: https://www.lw50.cn/article/4e2494d5dbece5a4e78691fc.html