基于坐标映射及多重图划分的图相似查询研究  

Research on Graph Similarity Query Based on CoordinateMapping and Multigraph Partition

作　　者：刘哲峰 梁平[1,2] 顾进广 LIU Zhe-feng;LIANG Ping;GU Jin-guang(School of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan 430065,China;Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System,Wuhan 430065,China)

机构地区：[1]武汉科技大学计算机科学与技术学院,湖北武汉430065 [2]智能信息处理与实时工业系统湖北省重点实验室,湖北武汉430065

出　　处：《计算机技术与发展》2023年第12期58-64,共7页Computer Technology and Development

基　　金：国家社会科学基金重大项目(11&ZD189)。

摘　　要：图相似查询是图数据库资源管理最重要的操作之一。目前的相似性查询算法几乎都是采用对整个图数据库进行过滤得到候选集的方式,没有考虑在实际图数据库中各数据图规模之间存在着一定的差距,没有必要对整个图数据库进行计算。因此,提出了一种基于坐标映射的批量处理方式,从规模上对数据图进行剔除,使得后续需要计算的数据图数量大大减少。同时给出了一个参数化的、基于选择性划分的GED下界,使得图划分方式具有约束性,而不是随机的,并在此基础上给出了一个多层索引结构,用于GED下限交叉检查。模拟实验结果表明,所提出的处理方法在通过坐标映射来尽量缩减计算时间的同时,较好地提升了过滤精度,甚至能在过滤阶段就得到相似查询的结果。Graph similarity search is one of the most important operations in graph database resource management.Currently,most similarity search algorithms filter the entire graph database to obtain a candidate set,without considering the significant differences in the size of the data graphs of the actual graph database,so it is not necessary to calculate the entire graph database.A batch processing method based on coordinate mapping is proposed to remove data graphs from the graph database,which greatly reduces the number of data graphs that need to be calculated subsequently.Moreover,a parameterized and selective partition-based GED lower bound is given to make the graph partitioning method constrained rather than random.Based on this,a multi-level index structure is provided for GED lower bound cross-checking.Simulation results show that the proposed processing method not only minimizes the calculation time through coordinate mapping but also improves filtering accuracy.Furthermore,it can even obtain the results of similarity queries in the filtering stage.

关 键 词：图数据库 图相似查询 坐标映射 选择性图划分 多层索引结构 

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