一种应用于大规模非规则结构数据的图搜索算法

摘要

本发明提出了一种应用于大规模非规则结构数据的图搜索算法，包括数据预处理方法和查询执行方法，其中数据预处理方法为：将非规则结构数据进行格式统一，为每个图的原图点构造一近邻标签向量表，构造具有属性点的扩充图；查询执行方法为：在原图数据点中利用一近邻标签筛选与关键点对应的候选匹配点，计算候选匹配点的匹配度并选择局部区域的中心点，在中心点周围划分出局部区域并查询子图和局部图的近似图匹配。该算法在保证搜索准确性的同时，大幅度降低运算复杂度，可以实现可行且有效的大规模非规则结构数据的图搜索。

主权项

一种应用于大规模非规则结构数据的图搜索算法，其特征在于，包括数据预处理方法和查询执行方法；数据预处理方法包括如下步骤：步骤S11，将非规则结构数据统一为一种图的数据格式作为原图；统一数据格式后的每个图中的点为原图点；步骤S12，为每个图的原图点构造一近邻标签向量表；步骤S13，在统一数据格式后的每个图中加入新的点作为属性点，并添加对应的边，形成具有属性点的扩充图；步骤S14，在扩充图上，使用重启动随机游走算法，以每个属性点为起点，计算属性点到每个原图点的概率。查询执行方法包括如下步骤：步骤S21，确定查询子图的关键性节点作为关键点，并在原图点中利用一近邻标签向量表筛选与关键点对应的点作为候选匹配点；步骤22，计算候选匹配点的匹配度，并根据匹配度大小选择局部区域的中心点；步骤23，在中心点周围进行局部区域的划分，利用松弛法进行查询子图和局部图的近似图匹配。