一种面向图集合的相似性搜索技术

目前图相似性的研究工作主要集中在子图的匹配,而没有充分关注图集合之间的匹配.针对这一问题,提出了一种基于过滤-求精框架的GSSS算法;提出了一种图集合距离定义,设计了Number,Size,Complete edge和Lower bound过滤器减小搜索空间,优化了图集合距离的计算;设计并优化了一种增量式的多层倒排索引,提高了查询效率,适应数据集的动态变化.真实数据集上的大量实验验证了GSSS算法的有效性和高效性.

A Similarity Search Technique for Graph Set

Existing studies of graph similarity search mainly focus on the subgraph matching instead of the graph set matching. To tackle this issue， GSSS algorithm was proposed based on filtering-and-verify framework. A graph set distance was defined. In order to reduce the search space， Number filter， Size filter， Complete edge filter and Lower bound filter were proposed. Then， the computation of the graph set distance was optimized. An incremental multi-layer inverted index was designed to further improve the query efficiency. Extensive experiments on a real-world dataset show that GSSS algorithm is effective and efficient.