高效低索引的图相似性搜索算法  

Graph Similarity Search with High Efficiency and Low Index

作　　者：邱珍 郑朝晖 QIU Zhen;ZHENG Zhaohui(School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China;Jiangsu Province Cyberspace Security Engineering Laboratory,Suzhou,Jiangsu 215006,China)

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215006 [2]江苏省网络空间安全工程实验室,江苏苏州215006

出　　处：《计算机科学》2023年第9期130-138,共9页Computer Science

基　　金：江苏省高校自然科学研究项目(19KJA550002)。

摘　　要：图相似性搜索是在给定的度量标准下查找与查询图相似的图集合,目前大多采用“过滤-验证”的计算框架。针对现有方法中过滤下界不紧密和索引空间占用较大等问题,提出了一种基于查询图分区的多层级过滤、低索引空间占用的图相似性搜索算法Z-Index。该算法首先通过全局粗粒度过滤得到预候选集;然后提出基于扩展概率的查询图分区算法,并采用层级过滤机制进一步精简候选集,增强下界紧密性;最后引入序列相似性差值计算序列中数据分布的稀疏度,提出分区压缩和差值压缩两种编码压缩算法,并据此构建“零”索引结构,降低索引空间开销。实验结果表明,Z-Index算法所得下界更加紧密,产生的候选集大小可减少50%左右,算法执行时间大大缩短,且该算法在索引空间占用极小的情况下仍具有可扩展性。Graph similarity search is to search the graph set that is similar to query graph under a measurement,which adopts the“filtering-verification”framework.Aiming at the problems of the existing methods,such as the untight lower bound and the large index space,an improved graph similarity search algorithm(Z-Index)based on query graph partition with multi-level filtering and low index space is proposed.Firstly,the pre-candidate set is obtained by global coarse-grained filtering.Secondly,a query graph partitioning algorithm based on extension probability is proposed,and a hierarchical filtering mechanism is adopted to further shrink the candidate set,so as to enhance the tightness of the lower bound.Finally,the sequence similarity difference is introduced to compute the sparsity of the data contribution.Then partition compression and difference compression algorithm are proposed to construct“zero”index structure,so as to reduce the index space.Experimental results show that Z-Index algorithm has a tighter lower bound,and the candidate set size of Z-Index can be reduced about 50%.Moreover,the algorithm execution time is greatly reduced,and it still shows great scalability in the case of tiny index space.

关 键 词：图相似性搜索 层级过滤 扩展概率 编码压缩 查询图分区 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]