计算机技术与发展2025，Vol.35Issue(7)：24-31,8.DOI:10.20165/j.cnki.ISSN1673-629X.2025.0073
多级过滤与分区均衡的图相似搜索研究
Research on Graph Similarity Search with Multi-level Filter and Partition Balance
摘要
Abstract
Graph similarity search refers to the process of searching for a set of data graphs from a graph database that meet the threshold requirements with respect to the query graph based on the graph edit distance.Since the calculation of graph edit distance is an NP-hard problem,the current mainstream algorithms mainly adopt the"filtering-verification"framework.The filtering algorithm is still based on the idea of partition index,which presents issues such as loose filtering lower bound,large candidate set size,lengthy filtering times,and unbalanced partition sizes during the partition filtering process.Therefore,corresponding improvement strategies for graph similarity search algorithms are proposed.Firstly,in the whole filtering stage,a multi-level filtering approach is employed.In the order of increasing cost,graph size,labels,vertex and adjacent edge label groups,and partition index are used for step-by-step filtering successively,and data graphs that do not meet the threshold requirements are gradually filtered out to reduce the candidate set generation overhead.Secondly,a heuristic method is provided to guide the initial vertex selection for partitioning,ensuring that the final partitions are as balanced as possible and improve the tightness of the partition filtering lower bound.Experimental results show that the proposed improvement strategies not only improve the tightness of the filtering lower bound,reduce the cost of partition index construction and the number of generated candidate graphs but also shorten the time of filtering stage and the overall time of graph similarity search.关键词
图相似搜索/图编辑距离/多级过滤/分区索引/分区均衡性Key words
graph similarity search/graph edit distance/multi-level filter/partition index/partition balance分类
信息技术与安全科学引用本文复制引用
赵旭,梁平,顾进广,高峰..多级过滤与分区均衡的图相似搜索研究[J].计算机技术与发展,2025,35(7):24-31,8.基金项目
国家重点研发计划重点专项(2022YFC3300801) （2022YFC3300801）
武汉市知识创新专项-曙光计划项目(2023010201020409) （2023010201020409）
