图近似查询算法研究

从数据管理中的近似查询方向,对图数据的近似查询算法进行了研究。依据近似查询的类别,分别介绍了近似查询中的经典算法,并对这些算法进行了详细的分析和讨论,从索引单元以及索引机制比较了各种算法适用的范围以及应用领域。重点阐述和比较了各算法的特点及查询性能,分析了各个算法存在的优势和不足。对近似查询中现有算法的不足及未来的研究方向进行了讨论。

基于回溯模式总结的鲁棒近似子图查询算法

为提高近似子图查询(匹配)的精度性和效率,提出一种模式总结重新匹配的近似子图查询算法。当部分嵌入被发现不能成为同构嵌入时,所提算法会生成失败模式。在回溯过程中,与失败模式进行匹配,对无用的部分嵌入进行剪枝,对所有的同构嵌入完成精确枚举。实验在酵母数据集和DBLP数据集上进行,比较无噪声和有结构噪声两种情形下的精确度,与卡方统计法和启发式算法相比,所提算法具有更高的精确度和鲁棒性。对于不同查询数,递归调用次数在10^(7)级,明显低于其它算法。