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

A Similarity Search Technique for Graph Set

作　　者：庞俊[1] 谷峪[1] 于戈[1] 

机构地区：[1]东北大学计算机科学与工程学院,辽宁沈阳110819

出　　处：《东北大学学报（自然科学版）》2017年第5期625-629,共5页Journal of Northeastern University(Natural Science)

基　　金：国家重点基础研究发展计划项目(2012CB316201);国家自然科学基金资助项目(61272179;61472071)

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

关 键 词：图集合 相似性 搜索 索引 过滤 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]