支持增量图数据的超图查询算法研究

Research on Supergraph Query Algorithm of Support Incremental Graph Data

当前大部分图查询算法都是针对静态图数据,不适用于现实应用中不断更新的图数据。针对这一问题,提出支持增量图数据的超图查询算法。该算法将数据图分解成直至单个顶点的子图,然后从单个顶点的子图开始求它到查询图的子图同构,直到求出数据图到查询图的子图同构结果,算法在数据图增加时只需将新加入的数据图进行分解即可,不必重新计算。通过分析证明,所提算法时间和空间复杂度不随数据图的增加而呈线性增长,节省了大量时间和空间代价。

Most current graph query algorithms are applicable for static graph data,but cannot be used in constantly updated map data in real world applications. Aiming at this problem,the supergraph query algorithm of support incremental map data is put forward. The data graph is divided into subgraphs with a single vertex by using the proposed algorithm,and then from the single vertex subgraph to find it＇s subgraph isomorphic to query graph,until the subgraph isomorphism results of data graph to query graph are found. When data graph increases,algorithm only needs to decomposition the newly added data graphs,and do not need to compute. The analysis shows that,the time and space complexity of proposed algorithm does not increase linearly with the increase of data graph,which saves much time and space costs.