基于坐标映射及多重图划分的图相似查询研究
Research on Graph Similarity Query Based on Coordinate Mapping and Multigraph Partition
刘哲峰 1梁平 1顾进广1
作者信息
- 1. 武汉科技大学 计算机科学与技术学院,湖北 武汉 430065;智能信息处理与实时工业系统湖北省重点实验室,湖北 武汉 430065
- 折叠
摘要
图相似查询是图数据库资源管理最重要的操作之一.目前的相似性查询算法几乎都是采用对整个图数据库进行过滤得到候选集的方式,没有考虑在实际图数据库中各数据图规模之间存在着一定的差距,没有必要对整个图数据库进行计算.因此,提出了一种基于坐标映射的批量处理方式,从规模上对数据图进行剔除,使得后续需要计算的数据图数量大大减少.同时给出了一个参数化的、基于选择性划分的GED下界,使得图划分方式具有约束性,而不是随机的,并在此基础上给出了一个多层索引结构,用于GED下限交叉检查.模拟实验结果表明,所提出的处理方法在通过坐标映射来尽量缩减计算时间的同时,较好地提升了过滤精度,甚至能在过滤阶段就得到相似查询的结果.
Abstract
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.
关键词
图数据库/图相似查询/坐标映射/选择性图划分/多层索引结构Key words
graph database/graph similarity search/coordinate mapping/selective map partitioning/multilayer index structure引用本文复制引用
基金项目
国家社会科学基金重大项目(11&ZD189)
出版年
2023
国家科技期刊平台
NSTL
维普
万方数据