基于双索引的近似子图匹配

越来越多的大型复杂网络使得图结构的研究变得日益重要，其中近似子图查询备受关注。为了提高查询效率，利用顶点的邻接关系特征为每个顶点建立索引，减少了匹配顶点的数量；并基于结构和标签对大型数据图进行划分，缩小了匹配时的搜索空间。利用离线时建立的双索引，查询时首先利用顶点间的近邻关系判定公式过滤掉大量不满足匹配关系的候选顶点，然后在一定的划分空间中进行边的匹配。真实数据集中的实验表明，与单纯的划分方法或近邻关系索引相比较，双索引机制对于查询的效率和准确率方面均有明显改善。

Approximate subgraph matching based on dual index

The fast increasing large and complex networks make the research of graph structure more and more important,in which approximate subgraph query is of big concern.Constructing index for each vertex by the adjacency characteristics was able to reduce the number of matched vertices,and partitioning the large graph based on label and structure information was able to reduce the matching search space.Using the dual index built in offline time,large amount of candidate vertices were filtered out according to the adjacency discriminant formula,and then the edge matching was carried out in some partition spaces.The experiments on real dataset show that,compared with many other existing methods,the dual-index query mechanism improves the efficiency and accuracy of subgraph matching significantly.